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
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int maxn = 100010; 4 struct arc{ 5 int to,w,next; 6 arc(int x = 0,int y = 0,int z = -1){ 7 to = x; 8 w = y; 9 next = z; 10 } 11 }e[maxn<<1]; 12 int head[maxn],tot; 13 void add(int u,int v,int w){ 14 e[tot] = arc(v,w,head[u]); 15 head[u] = tot++; 16 } 17 struct LCT{ 18 int fa[maxn],ch[maxn][2],sz[maxn]; 19 int key[maxn],pa[maxn],sum[maxn]; 20 inline void pushup(int x){ 21 sz[x] = 1 + sz[ch[x][0]] + sz[ch[x][1]]; 22 sum[x] = key[x] + sum[ch[x][0]] + sum[ch[x][1]]; 23 } 24 void rotate(int x,int kd){ 25 int y = fa[x]; 26 ch[y][kd^1] = ch[x][kd]; 27 fa[ch[x][kd]] = x; 28 fa[x] = fa[y]; 29 ch[x][kd] = y; 30 fa[y] = x; 31 if(fa[x]) ch[fa[x]][y == ch[fa[x]][1]] = x; 32 pushup(y); 33 } 34 void splay(int x,int goal){ 35 while(fa[x] != goal){ 36 if(fa[fa[x]] == goal) rotate(x,x == ch[fa[x]][0]); 37 else{ 38 int y = fa[x],z = fa[y],s = (y == ch[z][0]); 39 if(x == ch[y][s]){ 40 rotate(x,s^1); 41 rotate(x,s); 42 }else{ 43 rotate(y,s); 44 rotate(x,s); 45 } 46 } 47 } 48 pushup(x); 49 } 50 void access(int x){ 51 for(int y = 0; x; x = pa[x]){ 52 splay(x,0); 53 fa[ch[x][1]] = 0; 54 pa[ch[x][1]] = x; 55 ch[x][1] = y; 56 fa[y] = x; 57 y = x; 58 pushup(x); 59 } 60 } 61 int select(int x,int k){ 62 while(sz[ch[x][0]] + 1 != k){ 63 if(k < sz[ch[x][0]] + 1) x = ch[x][0]; 64 else{ 65 k -= sz[ch[x][0]] + 1; 66 x = ch[x][1]; 67 } 68 } 69 return x; 70 } 71 int kth(int y,int x,int k){ 72 access(y); 73 for(y = 0; x; x = pa[x]){ 74 splay(x,0); 75 if(!pa[x]){ 76 if(sz[ch[x][1]] + 1 == k) return x; 77 if(sz[ch[x][1]] + 1 > k) return select(ch[x][1],sz[ch[x][1]] - k + 1); 78 return select(y,k - sz[ch[x][1]] - 1); 79 } 80 fa[ch[x][1]] = 0; 81 pa[ch[x][1]] = x; 82 ch[x][1] = y; 83 fa[y] = x; 84 pa[y] = 0; 85 y = x; 86 pushup(x); 87 } 88 return 0; 89 } 90 int dis(int x,int y){ 91 access(y); 92 for(y = 0; x; x = pa[x]){ 93 splay(x,0); 94 if(!pa[x]) return sum[y] + sum[ch[x][1]]; 95 fa[ch[x][1]] = 0; 96 pa[ch[x][1]] = x; 97 ch[x][1] = y; 98 fa[y] = x; 99 pa[y] = 0; 100 y = x; 101 pushup(x); 102 } 103 return 0; 104 } 105 void build(int _val,int u,int v){ 106 sz[v] = 1; 107 ch[v][1] = ch[v][0] = fa[v] = 0; 108 pa[v] = u; 109 key[v] = sum[v] = _val; 110 } 111 }spt; 112 void dfs(int u,int fa){ 113 for(int i = head[u]; ~i; i = e[i].next){ 114 if(e[i].to == fa) continue; 115 spt.build(e[i].w,u,e[i].to); 116 dfs(e[i].to,u); 117 } 118 } 119 int main(){ 120 int kase,n,u,v,w; 121 char op[10]; 122 scanf("%d",&kase); 123 while(kase--){ 124 scanf("%d",&n); 125 memset(head,-1,sizeof head); 126 tot = 0; 127 for(int i = 1; i < n; ++i){ 128 scanf("%d%d%d",&u,&v,&w); 129 add(u,v,w); 130 add(v,u,w); 131 } 132 spt.build(0,0,1); 133 dfs(1,1); 134 while(scanf("%s",op) && op[1] != ‘O‘){ 135 if(op[1] == ‘I‘){ 136 scanf("%d%d",&u,&v); 137 if(u == v) puts("0"); 138 else printf("%d\n",spt.dis(u,v)); 139 }else if(op[1] == ‘T‘){ 140 scanf("%d%d%d",&u,&v,&w); 141 printf("%d\n",spt.kth(u,v,w)); 142 }else break; 143 } 144 puts(""); 145 } 146 return 0; 147 }
SPOJ QTREE2 Query on a tree II
原文：http://www.cnblogs.com/crackpotisback/p/4883195.html
