abc294G_驱动网

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

abc294G

2023-03-20 17:59:33 来源：博客园

【资料图】

Upd G

看上好模板的样子，果然是个~~模板题~~好题，首先考虑这张图的 $Euler \ Tour$, 简单点说，就是dfs一遍，把每个点入栈出栈顺序存起来，举个例子·

21 22 3

这棵树的 $Euler \ Tour$ 就是1 2 3 3 2 1

相当于把树拍成序列，之后在上面记录每个点到根的距离。

操作一改变某条边权值为 $w$ 相当于把这条边上入栈顺序相对靠后的点（son）的值改为 $w$ ，这个操作可以用树状数组/线段树维护。

操作二统计答案树上节点 $u \ v$ 的距离 $\operatorname{dis}(u, v) =\operatorname{dis}(1, u) + \operatorname{dis}(1, v) - 2 \times \operatorname{dis}(1, lca(u, v))$

所以找出 $u\ v $ 的 $lca$ 统计即可

$Code$

vector G[maxn];//LCA int p[maxn][21];int dep[maxn];int in[maxn], out[maxn];int T = 0;void dfs(int u, int fa, int depth) {    dep[u] = depth; p[u][0] = fa;    in[u] = ++T;    for (int i = 1; i <= 20; i++) p[u][i] = p[p[u][i - 1]][i - 1];    for (int i = 0; i < G[u].size(); i++) if (G[u][i] != fa) dfs(G[u][i], u, depth + 1);    out[u] = ++T;}int LCA(int x, int y) {    if (dep[x] < dep[y]) swap(x, y);    for (int i = 20; i >= 0; i--) if(dep[p[x][i]] >= dep[y]) x = p[x][i];    if (x == y) return x;    for (int i = 20; i >= 0; i--) if (p[x][i] != p[y][i]) x = p[x][i], y = p[y][i];    return p[x][0];}int lf[maxn], rf[maxn];int c[maxn], we[maxn];void add(int x, int y) {    for (int i = x; i <= T; i += i & (-i)) {        c[i] += y;     }    return;}int sum(int x) {    int res = 0;    for (int i = x; i; i -= i &-i) {        res += c[i];    }    return res;}signed main() {    cin >> n;    rep_(i, 1, n - 1) {        int u, v, w;        cin >> u >> v >> w;        G[u].pb(v);        G[v].pb(u);        lf[i] = u, rf[i] = v, we[i] = w;    }    dfs(1, 0, 1);    for (int i = 1; i <= n - 1; i++) {        if (in[lf[i]] > in[rf[i]]) swap(lf[i], rf[i]);        add(in[rf[i]], we[i]);        add(out[rf[i]], -we[i]);        }    int q;     cin >> q;    rep_(i, 1, q) {        int opt, x, y;        cin >> opt >> x >> y;        if (opt == 1) {            add(in[rf[x]], -we[x] + y);            add(out[rf[x]], we[x] - y);            we[x] = y;        } else {            cout << sum(in[x]) + sum(in[y]) - 2 * sum(in[LCA(x, y)]) << endl;        }    }

关键词：