You are given a tree (an undirected acyclic connected graph) with N nodes, and edges numbered 1, 2, 3...N-1. Each edge has an integer value assigned to it, representing its length.
We will ask you to perfrom some instructions of the following form:
Example:
N = 6
1 2 1 // edge connects node 1 and node 2 has cost 1
2 4 1
2 5 2
1 3 1
3 6 2
Path from node 4 to node 6 is 4 -> 2 -> 1 -> 3 -> 6
DIST 4 6 : answer is 5 (1 + 1 + 1 + 2 = 5)
KTH 4 6 4 : answer is 3 (the 4-th node on the path from node 4 to node 6 is 3)
The first line of input contains an integer t, the number of test cases (t <= 25). t test cases follow.
For each test case:
There is one blank line between successive tests.
For each "DIST" or "KTH" operation, write one integer representing its result.
Print one blank line after each test.
Input: 1 6 1 2 1 2 4 1 2 5 2 1 3 1 3 6 2 DIST 4 6 KTH 4 6 4 DONE Output: 5 3
#include <iostream> #include <cstring> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <time.h> #include <string> #include <map> #include <stack> #include <vector> #include <set> #include <queue> #define met(a,b) memset(a,b,sizeof a) #define pb push_back #define lson(x) ((x<<1)) #define rson(x) ((x<<1)+1) using namespace std; typedef long long ll; const int N=1e4+50; const int M=N*N+10; int n,m,k,tot=0; int fa[2*N][20],head[N*2],dis[N*2],dep[N*2]; struct man{ int to,next,w; }edg[2*N]; void add(int u,int v,int w){ edg[tot].to=v;edg[tot].next=head[u];edg[tot].w=w;head[u]=tot++; } void init(){ met(head,-1);met(fa,0);met(dis,0);met(dep,0); tot=0; } void dfs(int u,int f){ fa[u][0]=f; for(int i=1;i<20;i++){ fa[u][i]=fa[fa[u][i-1]][i-1]; } for(int i=head[u];i!=-1;i=edg[i].next){ int v=edg[i].to; if(v!=f){ dis[v]=dis[u]+edg[i].w; dep[v]=dep[u]+1; dfs(v,u); } } } int LCA(int u,int v){ int U=u,V=v; if(dep[u]<dep[v])swap(u,v); for(int i=19;i>=0;i--){ if(dep[fa[u][i]]>=dep[v]){ u=fa[u][i]; } } if(u==v)return (u); for(int i=19;i>=0;i--){ if(fa[u][i]!=fa[v][i]){ u=fa[u][i];v=fa[v][i]; } } return (fa[u][0]); } int find_kth(int u,int v,int lca,int k){ k--; if(dep[u]-dep[lca]<k){ k=dep[u]-dep[lca]*2+dep[v]-k; u=v; } for(int i=0;i<20;i++){ if(k&(1<<i)){ //注意这里 u=fa[u][i]; } } return u; } void solve(){ int u,v,val; scanf("%d",&n); for(int i=1;i<n;i++){ scanf("%d%d%d",&u,&v,&val); add(u,v,val);add(v,u,val); } dep[1]=1; dfs(1,0); char str[20]; while(1){ scanf("%s",str); if(str[0]==‘D‘&&str[1]==‘I‘){ scanf("%d%d",&u,&v); int lca=LCA(u,v); printf("%d\n",dis[u]+dis[v]-2*dis[lca]); } else if(str[0]==‘K‘){ scanf("%d%d%d",&u,&v,&k); int lca=LCA(u,v); printf("%d\n",find_kth(u,v,lca,k)); } else break; } } int main(){ int t; scanf("%d",&t); while(t--){ init(); solve(); } return 0; }
spoj 913 Query on a tree II (倍增lca)
原文：http://www.cnblogs.com/jianrenfang/p/6354452.html