//Accepted 11676 KB 2344 ms /* source:poj2763 time :2015.5.29 by :songt */ /*题解: 树链剖分 基于边权,路径查询 wind第一次在s节点,假如她走到了p节点,那么下次开始的时候他就在p节点 */ #include <cstdio> #include <cstring> ; struct Edge { int u,v; Edge(){} Edge(int u,int v):u(u),v(v){} }edge[*imax_n]; int head[imax_n]; *imax_n]; int tot; void addEdge(int u,int v) { edge[tot]=Edge(u,v); next[tot]=head[u]; head[u]=tot++; } int fa[imax_n],deep[imax_n],num[imax_n],son[imax_n]; int p[imax_n],fp[imax_n],top[imax_n]; int pos; void init() { memset(head,-,sizeof(head)); memset(next,-,sizeof(next)); tot=; memset(son,-,sizeof(son)); pos=; } int s[imax_n]; int cnt_s; int vis[imax_n]; void dfs1(int u) { fa[u]=; deep[u]=; cnt_s=; s[cnt_s++]=u; memset(vis,,sizeof(vis)); while (cnt_s) { ]; if (vis[x]) { cnt_s--; if (x!=u) { num[fa[x]]+=num[x]; || num[fa[x]]<num[x]) son[fa[x]]=x; } continue; } vis[x]=; num[x]=; ;i=next[i]) { int v=edge[i].v; if (v!=fa[x]) { fa[v]=x; deep[v]=deep[x]+; s[cnt_s++]=v; } } } } void dfs2(int u) { top[u]=u; memset(vis,,sizeof(vis)); cnt_s=; s[cnt_s++]=u; while (cnt_s) { ]; if (vis[x]) { cnt_s--; continue ; } vis[x]=; p[x]=pos++; fp[p[x]]=x; ) continue ; ;i=next[i]) { int v=edge[i].v; if (v!=fa[x] && v!=son[x]) { top[v]=v; s[cnt_s++]=v; } } top[son[x]]=top[x]; s[cnt_s++]=son[x]; } } struct Tree { int l,r; long long sum; }f[imax_n*]; void build(int t,int l,int r) { f[t].l=l; f[t].r=r; f[t].sum=; if (l==r) { return ; } ; build(*t,l,mid); build(*t+,mid+,r); } void update(int t,int k,int value) { if (f[t].l==k && f[t].r==k) { f[t].sum=value; return ; } ; *t,k,value); *t+,k,value); f[t].sum=f[*t].sum+f[*t+].sum; } long long query(int t,int l,int r) { if (f[t].l==l && f[t].r==r) { return f[t].sum; } ; *t,l,r); else { *t+,l,r); *t,l,mid)+query(*t+,mid+,r); } } void swap(int &a,int &b) { int t=a; a=b; b=t; } long long find(int u,int v) { int f1=top[u],f2=top[v]; ; while (f1!=f2) { if (deep[f1]<deep[f2]) { swap(f1,f2); swap(u,v); } sum+=query(,p[f1],p[u]); u=fa[f1]; f1=top[u]; } if (u==v) return sum; if (deep[u]>deep[v]) swap(u,v); sum+=query(,p[son[u]],p[v]); return sum; } ]; int n,m; int res; int main() { ) //scanf("%d%d%d",&n,&m,&res); { init(); ;i<n-;i++) { scanf(],&e[i][],&e[i][]); addEdge(e[i][],e[i][]); addEdge(e[i][],e[i][]); } dfs1(); dfs2(); build(,,pos-); ;i<n-;i++) { ]]<deep[e[i][]]) swap(e[i][],e[i][]); update(,p[e[i][]],e[i][]); } int kind; int u,v; ;i<m;i++) { scanf("%d",&kind); ) { scanf("%d",&u); printf("%lld\n",find(u,res)); res=u; } else { scanf("%d%d",&u,&v); update(,p[e[u-][]],v); } } } ; }