1.易知,树上两点的距离dis[u][v] = D[u]+D[v]-2*D[lca(u,v)] (D为节点到根节点的距离)
2.某条边<u,v>权值一旦改变,将会影响所有以v为根的子树上的节点到根节点的距离,很明显,DFS一遍后以v为根的子树在DFS序列中是连续的一段,及转化为区间更新问题,可以用树状数组。
做法:先把求LCA解决,LCA可以转化为RMQ问题,可参见:LCA转RMQ, 即转化为LCA(T,u,v) = RMQ(B,pos[u],pos[v]),其中B为深度序列。预先DFS可以处理出深度序列,我这里用的是“另一种”深度序列,即时间戳表示的深度序列,用时间戳来代表深度,以及欧拉序列和pos数组,还有in[],out[]数组,表示每个节点DFS进出的时间戳。在DFS时间戳序列上建树状数组,值为每个节点与原来到根节点的距离相比的该变量。要用树状数组需要用一个巧妙的方法转为前缀和问题:在时间戳序列中,如果要更新v的子树,即为更新in[v],out[v],令a = in[v],b=out[v],则可以令A[a] = delta,A[b+1] = -delta。然后更新,就可以用树状数组来查询了。然后每次求两点间距离的时候,结果为固定的dis[u][v]+变动的值(树状数组query求出)。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define N 100007 struct Edge { int u,v,w,next; }G[2*N]; int first[N],tot,n,Time,ind,ola[3*N],id; int pos[N],in[2*N],out[2*N],vis[3*N]; int d[2*N][24],dis[N],c[2*N],T[2*N],dp[3*N]; void RMQ_init() { int i,j; for(i=1;i<=id;i++) d[i][0] = dp[i]; for(j=1;(1<<j)<=id;j++) { for(i=1;i+(1<<j)-1<=id;i++) d[i][j] = min(d[i][j-1],d[i+(1<<(j-1))][j-1]); } } int RMQ(int l,int r) { int k = 0; while((1<<(k+1)) <= r-l+1) k++; return min(d[l][k],d[r-(1<<k)+1][k]); } void addedge(int u,int v,int w) { G[tot].u = u; G[tot].v = v; G[tot].w = w; G[tot].next = first[u]; first[u] = tot++; } void init() { memset(G,0,sizeof(G)); memset(first,-1,sizeof(first)); memset(c,0,sizeof(c)); memset(d,0,sizeof(d)); tot = 1; Time = 0; ind = 0; id = 0; } void DFS(int u,int fa) { ++Time; int deep = Time; ola[++ind] = u; T[Time] = u; dp[++id] = Time; in[u] = Time; for(int i=first[u];i!=-1;i=G[i].next) { int v = G[i].v; if(v == fa) continue; DFS(v,u); dp[++id] = deep; //深度序列 ola[++ind] = u; //欧拉序列 } //if(flag) //ola[++ind] = u; out[u] = Time; } void DFSWG(int u,int w,int fa) { dis[u] = w; for(int i=first[u];i!=-1;i=G[i].next) { int v = G[i].v; if(v == fa) continue; DFSWG(v,w+G[i].w,u); } } void Getpos() { memset(vis,0,sizeof(vis)); for(int i=1;i<=ind;i++) { if(!vis[ola[i]]) { vis[ola[i]] = 1; pos[ola[i]] = i; } } } int LCA(int u,int v) { int L = min(pos[u],pos[v]); int R = max(pos[u],pos[v]); return T[RMQ(L,R)]; } int lowbit(int x) { return x&(-x); } void update(int k,int num) { while(k <= n) { c[k] += num; k += lowbit(k); } } int query(int k) { int sum = 0; while(k > 0) { sum += c[k]; k -= lowbit(k); } return sum; } int main() { int i,j,u,v,w,op,q; scanf("%d",&n); { init(); for(i=0;i<n-1;i++) { scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } scanf("%d",&q); DFS(1,-1); Getpos(); RMQ_init(); DFSWG(1,0,-1); //算出dis while(q--) { scanf("%d%d%d",&op,&u,&v); if(op == 1) { int lca = LCA(u,v); printf("%d\n",dis[u]+dis[v]-2*dis[lca]+query(in[u])+query(in[v])-2*query(in[lca])); } else { int s = G[2*u-1].u; int t = G[2*u-1].v; if(pos[s] > pos[t]) //保证s是t的父亲 swap(s,t); int delta = v - G[2*u-1].w; G[2*u-1].w = G[2*u].w = v; //更新权值 update(in[t],delta); update(out[t]+1,-delta); } } } return 0; }
UESTC 912 树上的距离 --LCA+RMQ+树状数组,布布扣,bubuko.com
UESTC 912 树上的距离 --LCA+RMQ+树状数组
原文:http://www.cnblogs.com/whatbeg/p/3765632.html