因为重链剖分叫重女儿所以长链剖分叫长女儿。
O(nlogn)-O(1)求k级祖先,O(logn)求lca(也就是二分答案之后求k级祖先判定...),O(n)统计以深度为下标的信息。
性质1,总链长是O(n)数量级的。
写法跟树剖类似。
应用1:求k级祖先。
此处需要性质2:k级祖先所在长链,链长大于k。
值得注意的地方:len如果是最深深度,链长就是len - d。
母亲的d比女儿要小......经常写反。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <vector> 5 6 const int N = 300010; 7 8 inline void read(int &x) { 9 x = 0; 10 char c = getchar(); 11 while(c < ‘0‘ || c > ‘9‘) c = getchar(); 12 while(c >= ‘0‘ && c <= ‘9‘) { 13 x = (x << 3) + (x << 1) + c - 48; 14 c = getchar(); 15 } 16 return; 17 } 18 19 struct Edge { 20 int nex, v; 21 }edge[N << 1]; int tp; 22 23 int e[N], n, father[N][20], son[N], len[N], d[N], top[N], pw[N]; 24 std::vector<int> fa[N], af[N]; 25 26 inline void add(int x, int y) { 27 tp++; 28 edge[tp].v = y; 29 edge[tp].nex = e[x]; 30 e[x] = tp; 31 return; 32 } 33 34 void DFS_1(int x, int f) { /// get d father son len 35 father[x][0] = f; 36 d[x] = d[f] + 1; 37 len[x] = d[x]; 38 for(int i = e[x]; i; i = edge[i].nex) { 39 int y = edge[i].v; 40 if(y == f) { 41 continue; 42 } 43 DFS_1(y, x); 44 len[x] = std::max(len[x], len[y]); 45 if(len[y] > len[son[x]]) { 46 son[x] = y; 47 } 48 } 49 return; 50 } 51 52 void DFS_2(int x, int f) { /// get top fa 53 top[x] = f; 54 if(son[x]) { 55 DFS_2(son[x], f); 56 } 57 for(int i = e[x]; i; i = edge[i].nex) { 58 int y = edge[i].v; 59 if(y == father[x][0] || y == son[x]) continue; 60 DFS_2(y, y); 61 } 62 return; 63 } 64 65 inline void prework() { 66 for(int i = 2; i <= n; i++) pw[i] = pw[i >> 1] + 1; 67 for(int j = 1; j <= pw[n]; j++) { 68 for(int i = 1; i <= n; i++) { 69 father[i][j] = father[father[i][j - 1]][j - 1]; 70 } 71 } 72 for(int x = 1; x <= n; x++) { 73 if(top[x] != x) continue; 74 int up = x, down = x; 75 for(int i = 0; i <= len[x] - d[x]; i++) { 76 fa[x].push_back(up); 77 af[x].push_back(down); 78 up = father[up][0]; 79 down = son[down]; 80 } 81 } 82 return; 83 } 84 85 inline int ask(int x, int k) { 86 if(!k) return x; 87 if(k >= d[x] || k < 0) return 0; 88 int t = pw[k]; 89 x = father[x][t]; 90 if(!x) return 0; 91 k -= (1 << t); 92 int y = top[x]; 93 if(d[x] - d[y] >= k) { 94 return af[y][d[x] - d[y] - k]; 95 } 96 return fa[y][k - d[x] + d[y]]; 97 } 98 99 int main() { 100 int m; 101 read(n); 102 for(int i = 1, x, y; i < n; i++) { 103 read(x); read(y); 104 add(x, y); add(y, x); 105 } 106 DFS_1(1, 0); 107 DFS_2(1, 1); 108 prework(); 109 read(m); 110 int lastans = 0; 111 for(int i = 1, x, y; i <= m; i++) { 112 read(x); read(y); 113 lastans = ask(x ^ lastans, y ^ lastans); 114 printf("%d\n", lastans); 115 } 116 return 0; 117 }
应用2:统计信息。
原文:https://www.cnblogs.com/huyufeifei/p/10486192.html