Upd G
看上好模板的样子, 果然是个模板题 好题 , 首先考虑这张图的 \(Euler \ Tour\), 简单点说, 就是dfs一遍, 把每个点入栈出栈顺序存起来, 举个例子·
2
1 2
2 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<int> 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;
}
}
标签:int,abc294G,add,dep,rf,maxn,operatorname
From: https://www.cnblogs.com/Cranew/p/solution-at-abc294-g.html