| Time Limit: 433MS | Memory Limit: 1572864KB | 64bit IO Format: %lld & %llu |
Description
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
Hint
| Added by: | Thanh-Vy Hua |
| Date: | 2006-08-27 |
| Time limit: | 0.433s |
| Source limit: | 15000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ERL JS NODEJS PERL 6 VB.net |
| Resource: | Special thanks to Ivan Krasilnikov for his alternative solution |
有两种操作，一是求两点间距离，二是求一点到另一点路径上的第k个点。
LCA妥妥的。
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=10010; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 14 return x*f; 15 } 16 struct edge{ 17 int v,nxt,dis; 18 }e[mxn<<1]; 19 int hd[mxn],mct=0; 20 void add_edge(int u,int v,int d){ 21 e[++mct].v=v;e[mct].nxt=hd[u];e[mct].dis=d;hd[u]=mct;return; 22 } 23 int T,n; 24 int fa[mxn][15]; 25 int dep[mxn]; 26 int dis[mxn]; 27 void init(){memset(hd,0,sizeof hd);memset(fa,0,sizeof fa);mct=0;} 28 void DFS(int u,int f){ 29 dep[u]=dep[f]+1; 30 for(int i=1;i<15;i++)fa[u][i]=fa[fa[u][i-1]][i-1]; 31 for(int i=hd[u];i;i=e[i].nxt){ 32 int v=e[i].v; 33 if(v==f)continue; 34 fa[v][0]=u; 35 dis[v]=dis[u]+e[i].dis; 36 DFS(v,u); 37 } 38 return; 39 } 40 int LCA(int x,int y){ 41 if(dep[x]<dep[y])swap(x,y); 42 for(int i=14;i>=0;i--) 43 if(dep[fa[x][i]]>=dep[y])x=fa[x][i]; 44 if(x==y)return y; 45 for(int i=14;i>=0;i--){ 46 if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i]; 47 } 48 return fa[x][0]; 49 } 50 inline int dist(int x,int y){//求距离 51 int tmp=LCA(x,y); 52 return dis[x]+dis[y]-dis[tmp]*2; 53 } 54 inline int find(int x,int k){//上溯 55 for(int i=14;i>=0;i--){ 56 if(k&(1<<i))x=fa[x][i]; 57 } 58 return x; 59 } 60 inline int solve(int x,int y,int k){//查询从x到y路径上第k个结点 61 int tmp=LCA(x,y); 62 int mid=dep[x]-dep[tmp]+1; 63 if(k==mid)return tmp; 64 if(k>mid){ 65 int dd=dep[y]-dep[tmp]+1; 66 mid=k-mid+1; 67 k=dd-mid; 68 return find(y,k); 69 } 70 else 71 return find(x,k-1); 72 } 73 int main(){ 74 T=read(); 75 int i,j,x,y,d; 76 while(T--){ 77 init(); 78 n=read(); 79 for(i=1;i<n;i++){ 80 x=read();y=read();d=read(); 81 add_edge(x,y,d); 82 add_edge(y,x,d); 83 } 84 int rt=n/2+1; 85 dis[rt]=0; 86 DFS(rt,0); 87 char op[10]; 88 while(scanf("%s",op) && (op[0]!=‘D‘ || op[1]!=‘O‘)){ 89 if(op[0]==‘K‘){ 90 x=read();y=read();d=read(); 91 printf("%d\n",solve(x,y,d)); 92 } 93 if(op[0]==‘D‘){ 94 x=read();y=read(); 95 printf("%d\n",dist(x,y)); 96 } 97 } 98 } 99 return 0; 100 }
原文：http://www.cnblogs.com/SilverNebula/p/6098748.html