题意： 知道了一颗有 n 个节点的树和树上每条边的权值，对应两种操作：
0 x 输出 当前节点到 x节点的最短距离，并移动到 x 节点位置
1 x val 把第 x 条边的权值改为 val
题意： 知道了一颗有 n 个节点的树和树上每条边的权值，对应两种操作：
0 x 输出 当前节点到 x节点的最短距离，并移动到 x 节点位置
1 x val 把第 x 条边的权值改为 val
LCA +RMQ+树状数组
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm> using namespace std; const int maxn = 2e5+; int N,Q,S;
//vector <int> G[maxn]; struct edge{
int to,next,w;
}e[*maxn]; int head[*maxn],tot;
void add_edge(int u,int v,int w)
{
e[tot].to = v;
e[tot].w = w;
e[tot].next = head[u];
head[u] = tot++; e[tot].to = u;
e[tot].w = w;
e[tot].next = head[v];
head[v] = tot++;
} int in[maxn],out[maxn],P[*maxn],fa[maxn][],dep[maxn],dis[maxn],cnt;
void dfs(int u,int _fa,int _dep,int _dis)
{
in[u] = ++cnt;
P[cnt] = u;
fa[u][] = _fa;
dis[u] = _dis;
dep[u] = _dep;
for(int i=head[u];~i;i=e[i].next)
{
int v = e[i].to;
if(v == _fa) continue;
dfs(v,u,_dep+,_dis+e[i].w);
}
out[u] = ++cnt;
}
void debug()
{
printf("in:\t");for(int i=;i<=N;i++) printf("%d ",in[i]);puts("");
printf("out:\t");for(int i=;i<=N;i++) printf("%d ",out[i]);puts("");
printf("p:\t");for(int i=;i<=cnt;i++) printf("%d ",P[i]);puts("");
printf("dis:\t");for(int i=;i<=N;i++) printf("%d ",dis[i]);puts("");
printf("dep:\t");for(int i=;i<=N;i++) printf("%d ",dep[i]);puts("");
printf("edge:");for(int i=;i<tot;i++) printf("\tto:%d w:%d\n",e[i].to,e[i].w);
} int initLCA()
{
int m = (int)log(N)/log()+;
for(int k=;k<m;k++)
{
for(int v=;v<=N;v++)
{
if(fa[v][k] < ) {fa[v][k+] = -;continue;}
else fa[v][k+] = fa[fa[v][k]][k];
}
}
} int LCA(int u,int v)
{
int m = (int)log(N)/log()+;
if(dep[v] > dep[u]) swap(u,v);
for(int k=;k<m;k++)
{
if((dep[u]-dep[v])>>k & )
u = fa[u][k];
}
if(u == v) return u;
for(int k=m-;k>=;k--)
{
if(fa[u][k] != fa[v][k])
{
u = fa[u][k];
v = fa[v][k];
}
}
return fa[u][];
} int c[*maxn];
int lowbit(int x) {return x&-x;} void init()
{
memset(head,-,sizeof head);
memset(fa,-,sizeof fa);
memset(c,,sizeof c);
memset(in,,sizeof in);
memset(out,,sizeof out);
tot = ;
cnt = ;
} void add(int x,int d)
{
while(x)
{
c[x] += d;
x -= lowbit(x);
}
}
void add_seg(int l,int r,int d)
{
add(r,d);
add(l-,-d);
}
int sum(int x)
{
int res = ;
//printf("u:%d ",P[x]);
while(x <= cnt)
{
res += c[x];
x += lowbit(x);
}
//printf("res:%d\n",res);
return res;
}
int dist(int x)
{
if(x == -) return ;
return sum(in[x]) + dis[x];
}
int main()
{
//freopen("input.txt","r",stdin);
while(~scanf("%d%d%d",&N,&Q,&S))
{
init();
for(int i=,u,v,w;i<N-;i++)
{
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
}
dfs(,-,,);
//debug();
initLCA();
for(int i=;i<tot;i+=)
{
if(dep[e[i].to] < dep[e[i+].to]) swap(e[i].to,e[i+].to);
}
int op;
for(int i=,a,b,c;i<Q;i++)
{
scanf("%d",&op);
if(op == )
{
scanf("%d",&a);
int lca = LCA(S,a);
//printf("lca:%d\n",lca); printf("%d\n",dist(S)+dist(a)-*(dist(lca)));
S = a;
}else
{
scanf("%d%d",&a,&b);
a--;
int u = e[a*].to;
int dw = b - (dist(u) - dist(fa[u][]));
//printf("dw:%d u:%d\n",dw,u);
add_seg(in[u],out[u],dw);
}
}
}
}
树链部分
#include<cstdio>
#include<algorithm>
#include<cstring>
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
using namespace std;
typedef long long ll;
const int MAXN = 2e5 + ;
int n, q, s;
int fa[MAXN]; // fa[v]: v 的父亲
int dep[MAXN]; // dep[v]: v 的深度（根深度为１）
int siz[MAXN]; // : 以 v 为根的子树的节点数
int son[MAXN]; // : 重儿子，siz[u] 为 v 的子节点中 siz 值最大的，那么 u 就是 v 的重儿子
int top[MAXN]; // : 表示 v 所在的重链的顶端节点
int w[MAXN]; // : 表示 v 与其父亲节点的连边在线段树中的位置
int num; // 将树映射到线段树上的标号
int cnt, head[MAXN];
struct Edge {
int to, next;
}edge[MAXN];
struct E {
int u, v, c;
}e[MAXN];
void addedge(int u, int v) {
edge[cnt].to = v;
edge[cnt].next = head[u];
head[u] = cnt++;
}
void dfs(int u) {
siz[u] = ; son[u] = ;
for(int i = head[u]; ~i; i = edge[i].next) {
if(edge[i].to != fa[u]) {
fa[edge[i].to] = u;
dep[edge[i].to] = dep[u] + ;
dfs(edge[i].to);
if(siz[edge[i].to] > siz[son[u]]) son[u] = edge[i].to;
siz[u] += siz[edge[i].to];
}
}
}
void build_tree(int u, int tp) {
w[u] = ++num; top[u] = tp;
if(son[u]) build_tree(son[u], top[u]); // 使重链各边在线段树中呈连续分布
for(int i = head[u]; ~i; i = edge[i].next) {
int v = edge[i].to;
if(v != son[u] && v != fa[u])
build_tree(v, v);
}
}
ll sum[MAXN];
void pushUp(int rt) {
sum[rt] = sum[rt << ] + sum[rt << | ];
}
void build(int l, int r, int rt) {
sum[rt] = ;
if(l == r) return;
int m = (l + r) / ;
build(lson); build(rson);
}
void update(int p, int c, int l, int r, int rt) {
if(l == r) {
sum[rt] = c;
return;
}
int m = (l + r) / ;
if(m >= p) update(p, c, lson);
else update(p, c, rson);
pushUp(rt);
}
ll query(int L, int R, int l, int r, int rt) {
if(L <= l && R >= r) return sum[rt];
int m = (l + r) / ;
ll res = ;
if(m >= L) res += query(L, R, lson);
if(m < R) res += query(L, R, rson);
return res;
}
void change(int v, int c) {
if(dep[e[v].u] > dep[e[v].v]) update(w[e[v].u], c, , n, );
else update(w[e[v].v], c, , n, );
}
ll seek(int v, int u) {
int t1 = top[v], t2 = top[u];
ll res = ;
while(t1 != t2) {
if(dep[t1] < dep[t2]) {
swap(t1, t2); swap(v, u);
}
res += query(w[t1], w[v], , n, );
v = fa[t1]; t1 = top[v];
}
if(v == u) return res;
if(dep[v] > dep[u]) swap(v, u);
return res + query(w[son[v]], w[u], , n, );
}
int main() {
memset(head, -, sizeof head);
cnt = num = ;
scanf("%d%d%d", &n, &q, &s);
for(int i = ; i < n; i++) {
scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].c);
addedge(e[i].u, e[i].v);
addedge(e[i].v, e[i].u);
}
dfs();
build_tree(, );
build(, n, );
for(int i = ; i < n; i++) {
if(dep[e[i].u] > dep[e[i].v]) update(w[e[i].u], e[i].c, , n, );
else update(w[e[i].v], e[i].c, , n, );
}
while(q--) {
int cc;
int x, y;
scanf("%d", &cc);
if(cc) {
scanf("%d%d", &x, &y);
change(x, y);
} else {
scanf("%d", &x);
printf("%lld\n", seek(s, x));
s = x;
}
}
return ;
}