解题思路
本题只有两种操作:求树上两点间路径的权值和、修改边权。
于是使用树链剖分就很简单了。
参考代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
const int MAXN = 100001;
struct edge_orig {
int u, v;
int w;
} edge[MAXN];
struct edge {
int to;
int next;
} e[MAXN<<1];
int n, q, s, a, b, op;
int fa[MAXN], dep[MAXN], sz[MAXN], son[MAXN];
int idx, id[MAXN], top[MAXN], val[MAXN];
int head[MAXN], cnt;
int SUM[MAXN<<2];
void Add(int u, int v) {
e[cnt].to = v;
e[cnt].next = head[u];
head[u] = cnt++;
}
void DFS1(int u, int pre, int d) {
dep[u] = d;
sz[u] = 1;
son[u] = 0;
fa[u] = pre;
for(int i=head[u]; ~i; i=e[i].next) {
int v = e[i].to;
if(v != pre) {
DFS1(v, u, d+1);
sz[u] += sz[v];
if(sz[v] > sz[son[u]])
son[u] = v;
}
}
}
void DFS2(int u, int t) {
top[u] = t;
id[u] = ++idx;
if(son[u]) DFS2(son[u], t);
for(int i=head[u]; ~i; i=e[i].next) {
int v = e[i].to;
if(v!=fa[u] && v!=son[u])
DFS2(v, v);
}
}
void PushUp(int rt) {
SUM[rt] = SUM[rt<<1] + SUM[rt<<1|1];
}
void Build(int l, int r, int rt) {
if(l == r) {
SUM[rt] = val[l];
return;
}
int m = (l + r) >> 1;
Build(lson);
Build(rson);
PushUp(rt);
}
void Update(int p, int v, int l, int r, int rt) {
if(l == r) {
SUM[rt] = v;
return;
}
int m = (l + r) >> 1;
if(p <= m) Update(p, v,lson);
else Update(p, v, rson);
PushUp(rt);
}
int Query(int L, int R, int l, int r, int rt) {
if(L<=l && r<=R) return SUM[rt];
int m = (l + r) >> 1;
int ret = 0;
if(L <= m) ret += Query(L, R, lson);
if(R > m) ret += Query(L, R, rson);
return ret;
}
int GetAns(int u, int v) {
int ans = 0;
while(top[u] != top[v]) {
if(dep[top[u]] < dep[top[v]])
swap(u, v);
ans += Query(id[top[u]], id[u], 1, n, 1);
u = fa[top[u]];
}
if(u == v) return ans;
if(dep[u] > dep[v]) swap(u, v);
ans += Query(id[son[u]], id[v], 1, n, 1);
return ans;
}
int main(int argc, char const *argv[]) {
memset(head, -1, sizeof head);
scanf("%d %d %d", &n, &q, &s);
for(int i=1; i<=n-1; ++i) {
scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].w);
Add(edge[i].u, edge[i].v);
Add(edge[i].v, edge[i].u);
}
idx = 0;
DFS1(1, -1, 1);
DFS2(1, 1);
for(int i=1; i<=n-1; ++i) {
if(dep[edge[i].u] < dep[edge[i].v])
swap(edge[i].u, edge[i].v);
val[id[edge[i].u]] = edge[i].w;
}
Build(1, n, 1);
while(q--) {
scanf("%d", &op);
if(op == 0) {
scanf("%d", &a);
printf("%d\n", GetAns(s, a));
s = a;
}
else {
scanf("%d %d", &a, &b);
Update(id[edge[a].u], b, 1, n, 1);
}
}
return 0;
}
还不快抢沙发