首页 > 其他 > 详细

长链剖分

时间:2019-03-06 23:12:18      阅读:244      评论:0      收藏:0      [点我收藏+]

因为重链剖分叫重女儿所以长链剖分叫长女儿。

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 }
AC代码

应用2:统计信息。

长链剖分

原文:https://www.cnblogs.com/huyufeifei/p/10486192.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!