/**//* 本题给定一棵带边权的树,要求支持两种操作: 询问树中某两点间的距离,修改某条边的权值。 假设没有修改操作,就可以直接转化为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; }
|