HDU 2586 How far away ？
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2586 题解 检验模板系列 LCA求树上任意亮点距离 代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 |
//while(true) RP++; #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<set> #define LL long long using namespace std; const int Maxn=40000; const int Maxd=20; struct Edge{ int v,nxt; LL dis; Edge(){} Edge(int v0,int n0,LL d0){ v=v0; nxt=n0; dis=d0; } }; Edge e[Maxn*2+5]; int head[Maxn+5]; int nume; inline void addEdge(int u,int v,LL dis){ e[++nume]=Edge(v,head[u],dis); head[u]=nume; e[++nume]=Edge(u,head[v],dis); head[v]=nume; } int fa[Maxn+5][25]; int dep[Maxn+5]; LL dis[Maxn+5]; void dfs(int x){ for (int i=1;i<=Maxd;i++) fa[x][i]=fa[fa[x][i-1]][i-1]; for (int i=head[x];i;i=e[i].nxt){ int v=e[i].v; if (fa[v][0]) continue; fa[v][0]=x; dep[v]=dep[x]+1; dis[v]=dis[x]+e[i].dis; dfs(v); } } inline void swim(int &x,int t){ for (int i=0;t;t/=2,i++) if (t&1) x=fa[x][i]; } inline int LCA(int x,int y){ if (dep[x]<dep[y]) swap(x,y); swim(x,dep[x]-dep[y]); if (x==y) return x; for (int i=Maxd;i>=0;i--){ if (fa[x][i]==fa[y][i]) continue; x=fa[x][i]; y=fa[y][i]; } return fa[x][0]; } int n,m; inline LL getDist(int x,int y){ int lca=LCA(x,y); //printf("GetDist %d %d %lld\n",x,y,dis[x]+dis[y]-dis[lca]*2LL); return dis[x]+dis[y]-dis[lca]*2LL; } void solve(){ memset(dep,0,sizeof(dep)); memset(dis,0,sizeof(dis)); memset(fa,0,sizeof(fa)); memset(head,0,sizeof(head)); nume=0; scanf("%d%d",&n,&m); for (int i=1;i<n;i++){ int x,y; LL d; scanf("%d%d%lld",&x,&y,&d); addEdge(x,y,d); } fa[1][0]=1; dep[1]=1; dis[1]=0; dfs(1); for (int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); printf("%lld\n",getDist(x,y)); //printf("%d\n",(*tree.end()).index); } } int main(){ int T=0; while(scanf("%d",&T)!=EOF) for(int i=1;i<=T;i++) solve(); } |
