首页 > 代码库 > 树链剖分

树链剖分

2024-08-16 23:38:28   228人阅读

本蒟蒻今天开始刷BZOJ

本来准备愉快的水完降序排列的一波题  。。结果。。我果然是个弱菜

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1036

上网搜了一下，可以用树链剖分解决，正好我不会，就学了一下。

深吸一口，我要开始转述了，

 

树链剖分可以把树的边分为轻、重边

重边：与子树子节点最多的子节点连成的边；

轻边：不是重边的边

发现这样干讲仿佛说的都是些没营养的东西，还是让我们结合题目代码来说吧（微笑微笑）

 

[cpp] view plain copy
 
  1. #include <stdio.h>  
  2. #include <string.h>  
  3. #include <iostream>  
  4. #include <algorithm>  
  5. #include <vector>  
  6. #include <queue>  
  7. #include <set>  
  8. #include <map>  
  9. #include <string>  
  10. #include <math.h>  
  11. #include <stdlib.h>  
  12. using namespace std;  
  13.   
  14. const int MAXN = 30010;  
  15. struct Edge  
  16. {  
  17.     int to,next;  
  18. }edge[MAXN*2];  
  19. int head[MAXN],tot;  
  20. int top[MAXN]; //top[v] 表示v所在的重链的顶端节点  
  21. int fa[MAXN]; //父亲节点  
  22. int deep[MAXN];//深度  
  23. int num[MAXN]; //num[v]表示以v为根的子树的节点数  
  24. int p[MAXN]; //p[v]表示v在线段树中的位置  
  25. int fp[MAXN];//和p数组相反  
  26. int son[MAXN];//重儿子  
  27. int pos;  
  28. void init()  
  29. {  
  30.     tot = 0;  
  31.     memset(head,-1,sizeof(head));  
  32.     pos = 0;  
  33.     memset(son,-1,sizeof(son));  
  34. }  
  35. void addedge(int u,int v)  
  36. {  
  37.     edge[tot].to = v; edge[tot].next = head[u]; head[u] = tot++;//链式前向星存图  
  38. }  
  39. void dfs1(int u,int pre,int d) //第一遍dfs求出fa,deep,num,son  
  40. {  
  41.     deep[u] = d;  
  42.     fa[u] = pre;  
  43.     num[u] = 1;  
  44.     for(int i = head[u];i != -1;i = edge[i].next)  
  45.     {  
  46.         int v = edge[i].to;  
  47.         if(v != pre)  
  48.         {  
  49.             dfs1(v,u,d+1);  
  50.             num[u] += num[v];  
  51.             if(son[u] == -1 || num[v] > num[son[u]])  
  52.                 son[u] = v;  
  53.         }  
  54.     }  
  55. }  
  56. void getpos(int u,int sp)  
  57. {  
  58.     top[u] = sp;  
  59.     p[u] = pos++;  
  60.     fp[p[u]] = u;  
  61.     if(son[u] == -1) return;  
  62.     getpos(son[u],sp);//使重链上的节点在线段树中是连续的  
  63.     for(int i = head[u]; i != -1 ; i = edge[i].next)  
  64.     {  
  65.         int v = edge[i].to;  
  66.         if(v != son[u] && v != fa[u]) getpos(v,v);//加入轻链  
  67.     }  
  68. }  
  69.   
  70. struct Node  
  71. {  
  72.     int l,r;  
  73.     int sum;  
  74.     int Max;  
  75. }segTree[MAXN*3];  
  76. void push_up(int i)  
  77. {  
  78.     segTree[i].sum = segTree[i<<1].sum + segTree[(i<<1)|1].sum;  
  79.     segTree[i].Max = max(segTree[i<<1].Max,segTree[(i<<1)|1].Max);  
  80. }   
  81. int s[MAXN];  
  82. void build(int i,int l,int r)  
  83. {  
  84.     segTree[i].l = l;  
  85.     segTree[i].r = r;  
  86.     if(l == r)  
  87.     {  
  88.         segTree[i].sum = segTree[i].Max = s[fp[l]];  
  89.         return ;  
  90.     }  
  91.     int mid = (l + r)/2;  
  92.     build(i<<1,l,mid);  
  93.     build((i<<1)|1,mid+1,r);  
  94.     push_up(i);  
  95. }  
  96. void update(int i,int k,int val)//更新线段树的第k个值为val  
  97. {  
  98.     if(segTree[i].l == k && segTree[i].r == k)  
  99.     {  
  100.         segTree[i].sum = segTree[i].Max = val;  
  101.         return;  
  102.     }  
  103.     int mid = (segTree[i].l + segTree[i].r)/2;  
  104.     if(k <= mid)update(i<<1,k,val);  
  105.     else update((i<<1)|1,k,val);  
  106.     push_up(i);  
  107. }  
  108. int queryMax(int i,int l,int r)//查询线段树[l,r]区间的最大值  
  109. {  
  110.     if(segTree[i].l == l && segTree[i].r == r)  
  111.     {  
  112.         return segTree[i].Max;  
  113.     }  
  114.     int mid = (segTree[i].l + segTree[i].r)/2;  
  115.     if(r <= mid) return queryMax(i<<1,l,r);  
  116.     else if(l > mid)return queryMax((i<<1)|1,l,r);  
  117.     else return max(queryMax(i<<1,l,mid),queryMax((i<<1)|1,mid+1,r));  
  118. }  
  119. int querySum(int i,int l,int r) //查询线段树[l,r]区间的和  
  120. {  
  121.     if(segTree[i].l == l && segTree[i].r == r)  
  122.         return segTree[i].sum;  
  123.     int mid = (segTree[i].l + segTree[i].r)/2;  
  124.     if(r <= mid)return querySum(i<<1,l,r);  
  125.     else if(l > mid)return querySum((i<<1)|1,l,r);  
  126.     else return querySum(i<<1,l,mid) + querySum((i<<1)|1,mid+1,r);  
  127. }  
  128. int findMax(int u,int v)//查询u->v路径上节点的最大权值  
  129. {  
  130.     int f1 = top[u] , f2 = top[v];  
  131.     int tmp = -1000000000;  
  132.     while(f1 != f2)  
  133.     {  
  134.         if(deep[f1] < deep[f2])  
  135.         {  
  136.             swap(f1,f2);  
  137.             swap(u,v);  
  138.         }  
  139.         tmp = max(tmp,queryMax(1,p[f1],p[u]));//查询u所在重链的顶端节点->u路径上节点的最大值  
  140.         u = fa[f1];//u更新为u所在重链的顶端节点的父亲节点  
  141.         f1 = top[u];  
  142.     }  
  143.     if(deep[u] > deep[v]) swap(u,v);  
  144.     return max(tmp,queryMax(1,p[u],p[v]));//查询u(即之前<span style="font-family: Arial, Helvetica, sans-serif;">u所在重链的顶端节点的父亲节点）</span>->v路径上节点的最大值；  
  145. }  
  146. int findSum(int u,int v) //查询u->v路径上节点的权值的和  
  147. {  
  148.     int f1 = top[u], f2 = top[v];  
  149.     int tmp = 0;  
  150.     while(f1 != f2)  
  151.     {  
  152.         if(deep[f1] < deep[f2])  
  153.         {  
  154.             swap(f1,f2);  
  155.             swap(u,v);  
  156.         }  
  157.         tmp += querySum(1,p[f1],p[u]);  
  158.         u = fa[f1];  
  159.         f1 = top[u];  
  160.     }  
  161.     if(deep[u] > deep[v]) swap(u,v);  
  162.     return tmp + querySum(1,p[u],p[v]);  
  163. }  
  164. int main()   
  165. {  
  166.     //freopen("in.txt","r",stdin);  
  167.     //freopen("out.txt","w",stdout);  
  168.     int n;  
  169.     int q;  
  170.     char op[20];  
  171.     int u,v;  
  172.     while(scanf("%d",&n) == 1)  
  173.     {  
  174.         init();  
  175.         for(int i = 1;i < n;i++)  
  176.         {  
  177.             scanf("%d%d",&u,&v);  
  178.             addedge(u,v);  
  179.             addedge(v,u);  
  180.         }  
  181.         for(int i = 1;i <= n;i++)  
  182.             scanf("%d",&s[i]);  
  183.         dfs1(1,0,0);  
  184.         getpos(1,1);  
  185.         build(1,0,pos-1);  
  186.         scanf("%d",&q);  
  187.         while(q--)  
  188.         {  
  189.             scanf("%s%d%d",op,&u,&v);  
  190.             if(op[0] == ‘C‘)  
  191.                 update(1,p[u],v);//修改单点的值  
  192.             else if(strcmp(op,"QMAX") == 0)  
  193.                 printf("%d\n",findMax(u,v));//查询u->v路径上点权的最大值  
  194.             else printf("%d\n",findSum(u,v));//查询路径上点权的和  
  195.         }  
  196.     }  
  197.     return 0;  
  198. }  

 

完结撒花??????

树链剖分


联系
我们