首页 > 代码库 > UESTC 912 树上的距离 --LCA+RMQ+树状数组
UESTC 912 树上的距离 --LCA+RMQ+树状数组
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 100007struct 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;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。