专栏文章

【MX-S7-T2】「SMOI-R2」Speaker题解

cconsequence
P11324题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mir0kqnc
此快照首次捕获于
2025/12/04 13:47
3 个月前
此快照最后确认于
2025/12/04 13:47
3 个月前
查看原文

【MX-S7-T2】「SMOI-R2」Speaker 题解

先考虑特殊性质 CC。
设 11 为根节点。
设 dpxdp_x 表示以 xx 为根的子树所能贡献的最大值，对于 xx 的一个孩子 ss，设它们之间的距离为 dd，显然有转移：dpx=max⁡dps−2ddp_x = \max dp_s - 2d。
dpxdp_x 的初值为 cxc_x。
对于一个点对 (a,b)(a, b)，设两点间的路径为 AA，答案就应当是 ca+cb+max⁡i∈Adpi−disa,bc_a + c_b + \max\limits_{i \in A} dp_i - dis_{a, b}，树剖后用 ST 表维护路径上最大值即可。
再考虑一般情况。
相较于特殊情况，一般情况的答案还可能是在 lcaa,blca_{a, b} 到根节点的路径上的某个点的子树上的点演出。
设 fdpxfdp_x 表示点 xx 在这种情况下的答案的答案，设 pp 为 xx 的父亲，有转移 fdpx=max⁡(cx,fdpp−2disx,p)fdp_x = \max(c_x, fdp_p - 2dis_{x, p})。
fdpxfdp_x 的初值为 dpxdp_x。
最后答案即为 ca+cb+max⁡i∈A(dpi,fdplcaa,b)−disa,bc_a + c_b + \max\limits_{i \in A} (dp_i,fdp_{lca_{a, b}}) - dis_{a, b}。
时间复杂度 O(nlog⁡n)O(n \log n)。

丑陋的赛时 AC 代码：

CPP
#include <bits/stdc++.h>
#define mp make_pair
#define fr first
#define sc second

using namespace std;

typedef pair<long long, int> pii;
const int MAXN = 2e5 + 10;
vector<pii> v[MAXN];
long long st[MAXN][24 + 5];
long long dp[MAXN], c[MAXN], fdp[MAXN], dis[MAXN];
int f[MAXN], d[MAXN], sz[MAXN], son[MAXN], top[MAXN], id[MAXN];
int n, q, cnt;

long long ask(int l, int r) {
	int k = log(r - l + 1) / log(2);
	return max(st[l][k], st[r - (1 << k) + 1][k]);
}
long long query(int x, int y) {
    long long val = LLONG_MIN;
    int fx = x, fy = y;
    while (top[x] != top[y]) {
        if (d[top[x]] < d[top[y]]) swap(x, y);
        val = max(val, ask(id[top[x]], id[x]));
        x = f[top[x]];
    }
    if (d[x] > d[y]) swap(x, y);
    val = max(val, ask(id[x], id[y]));
    val = max(val, fdp[id[x]]);
    return val + 2 * dis[x] - dis[fx] - dis[fy] + c[fx] + c[fy];
}
void dfs1(int x, int p) {
    d[x] = d[p] + 1;
    f[x] = p;
    int maxson = -1;
    for (int i = 0; i < v[x].size(); ++i) {
        int nx = v[x][i].sc;
        if (nx == p) continue;
        dis[nx] = dis[x] + v[x][i].fr;
        dfs1(nx, x);
        sz[x] += sz[nx];
        if (sz[nx] > maxson) {
            maxson = sz[nx];
            son[x] = nx;
        }
    }
    sz[x]++;
}
void dfs2(int x, int ntop) {
    id[x] = ++cnt;
    top[x] = ntop;
    if (!son[x]) return;
    dfs2(son[x], ntop);
    for (int i = 0; i < v[x].size(); ++i) {
        int nx = v[x][i].sc;
        if (nx == f[x] || nx == son[x]) continue;
        dfs2(nx, nx);
    }   
}
void dfs3(int x, int p) {
    dp[id[x]] = c[x];
    for (int i = 0; i < v[x].size(); ++i) {
        int nx = v[x][i].sc;
        if (nx == p) continue;
        dfs3(nx, x);
        dp[id[x]] = max(dp[id[x]], dp[id[nx]] - 2 * v[x][i].fr);
    }
    fdp[id[x]] = dp[id[x]];
}
void dfs4(int x, int p) {
    for (int i = 0; i < v[x].size(); ++i) {
        int nx = v[x][i].sc;
        if (nx == p) {
            fdp[id[x]] = max(fdp[id[x]], fdp[id[nx]] - 2 * v[x][i].fr);
            break;
        }
    }
    for (int i = 0; i < v[x].size(); ++i) {
        int nx = v[x][i].sc;
        if (nx == p) continue;
        dfs4(nx, x);
    }
}

int main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> c[i];
    for (int i = 1; i < n; ++i) {
        int a, b;
        long long nd;
        cin >> a >> b >> nd;
        v[a].push_back(mp(nd, b));
        v[b].push_back(mp(nd, a));
    }
    dfs1(1, 1);
    dfs2(1, 1);
    //树链剖分
    dfs3(1, 1);//转移dp
    dfs4(1, 1);//转移fdp，其实可以在建ST表时直接用fdp
    int maxk = log(n) / log(2) + 1;
    for (int i = 1; i <= n; ++i) st[i][0] = dp[i];
    for (int j = 1; j <= maxk; ++j) {
		for (int i = 1; i + (1 << j) <= n + 1; ++i) {
			st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
		}
	}//ST表
    for (int i = 1; i <= q; ++i) {
        int a, b;
        cin >> a >> b;
        cout << query(a, b) << "\n";
    }
    return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...