 /**//*
本题给定一棵带边权的树,要求支持两种操作:
询问树中某两点间的距离,修改某条边的权值。
假设没有修改操作,就可以直接转化为LCA问题解决:dist[u]+dist[v]-2*dist[lca]
对于修改a--fa[a]操作,a及其儿子到根的距离都会被改变
所以对每一次修改操作,更新a及其儿子的偏移量
最后查询时,到根的距离就为dist[a]+chg[a]
我这里是直接修改
用线段树对这欧拉序列一整段修改会快点吧
*/
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;

const int MAXN = 100005;

struct Node
  {
int u,v,w,next;
}nodes[MAXN*2];

int G[MAXN],pa[MAXN],chg[MAXN],dist[MAXN];
int rmq[MAXN*2][20];
int F[MAXN*2],B[2*MAXN],beg[MAXN],end[MAXN],level[MAXN];
int alloc,done;

void add(int a ,int b,int c)
  {
alloc++;
nodes[alloc].u=a,nodes[alloc].v=b,nodes[alloc].w=c;
nodes[alloc].next=G[a];
G[a]=alloc;
}
 void dfs(int u,int p,int dep) {
done++;
F[done]=u,B[done]=dep,beg[u]=done;
pa[u]=p;level[u]=dep;
 for(int son=G[u];son;son=nodes[son].next) {
int v=nodes[son].v,w=nodes[son].w;
if(v==p)continue;
dist[v]=dist[u]+w;
dfs(v,u,dep+1);
done++;
F[done]=u,B[done]=dep;
}
//end[u]=done;
}
void initRMQ()
  {
for(int i=1;i<=done;i++)rmq[i][0]=i;
for(int j=1;(1<<j)<=done;j++)
for(int i=1;i+(1<<j)-1<=done;i++)
if(B[rmq[i][j-1]]<B[rmq[i+(1<<(j-1))][j-1]])rmq[i][j]=rmq[i][j-1];
else rmq[i][j]=rmq[i+(1<<(j-1))][j-1];
}
inline int LCA(int a,int b)
  {
a=beg[a],b=beg[b];
if(a>b)swap(a,b);
int k = log(1.0+b-a)/log(2.0);
if(B[rmq[a][k]]<B[rmq[b-(1<<k)+1][k]])return F[rmq[a][k]];
else return F[rmq[b-(1<<k)+1][k]];
}
void update(int x,int delta)
  {
chg[x]+=delta;
 for(int son=G[x];son;son=nodes[son].next) {
int v=nodes[son].v;
if(v==pa[x])continue;
update(v,delta);
}
}
int main()
  {
//freopen("in","r",stdin);
int N,Q,S;
 while(~scanf("%d%d%d",&N,&Q,&S)) {
memset(G+1,0,sizeof(int)*N);
memset(chg+1,0,sizeof(int)*N);
done = alloc = 0;
int a,b,c;
 for(int i=1;i<N;i++) {
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
dfs(1,0,0);
initRMQ();
 for(int i=1;i<=Q;i++) {
int c,a,b;
scanf("%d%d",&c,&b);
 if(c==1) {
b<<=1;
scanf("%d",&a);
c = a-nodes[b].w;
nodes[b].w+=c;
update(level[nodes[b].u]>level[nodes[b].v]?nodes[b].u:nodes[b].v,c);
}
 else {
int lca = LCA(S,b);
printf("%d\n",dist[S]+chg[S]+dist[b]+chg[b]-2*(dist[lca]+chg[lca]));
S=b;
}
}
}
return 0;
}
|