[关闭]
@xunuo 2017-02-25T13:54:20.000000Z 字数 3713 阅读 992

树的统计Count


Time Limit: 10 Sec  Memory Limit: 162 MB

树链剖分


Description

 一棵树上有n个节点,编号分别为1到n,每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作: I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 I
II. QSUM u v: 询问从点u到点v的路径上的节点的权值和 注意:从点u到点v的路径上的节点包括u和v本身

Input

  输入的第一行为一个整数n,表示节点的个数。接下来n – 1行,每行2个整数a和b,表示节点a和节点b之间有
一条边相连。接下来n行,每行一个整数,第i行的整数wi表示节点i的权值。接下来1行,为一个整数q,表示操作
的总数。接下来q行,每行一个操作,以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。 
对于100%的数据,保证1<=n<=30000,0<=q<=200000;中途操作中保证每个节点的权值w在-30000到30000之间。

Output

  对于每个“QMAX”或者“QSUM”的操作,每行输出一个整数表示要求输出的结果。

Sample Input

4
1 2
2 3
4 1
4 2 1 3
12
QMAX 3 4
QMAX 3 3
QMAX 3 2
QMAX 2 3
QSUM 3 4
QSUM 2 1
CHANGE 1 5
QMAX 3 4
CHANGE 3 6
QMAX 3 4
QMAX 2 4
QSUM 3 4

Sample Output

4
1
2
2
10
6
5
6
5
16

解题思路:

这里要求的有:查询区间最大值:qmax,区间求和:qsum,单点修改change;
1)、查询区间最大值:
        如果要查询的u和v不在同一重链上,则先判断top[u]和top[v]的深度,在深度较深的那个重链上直接查询(tid[top[v]],tid[v])区间的最大值后将v跳fa[top[v]]上,直到u,v在同一条重链上,再进行查询这条重链上的最大值;
2)、区间求和:
    也是与区间求最大值差不多,若u与v不再同一重链上,则先判断top[u]和top[v]的深度,在深度较深的那个重链上直接求(tid[top[v]],tid[v])区间的和后将v跳fa[top[v]]上,直到u,v在同一条重链上,再进行求这条重链上的和;
3)、单点修改:
    当查到这个点时,将它的值改为新的num;按照线段树来~~

完整代码:

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<math.h>
  4. #include<algorithm>
  5. #include<vector>
  6. using namespace std;
  7. #define N 30010
  8. #define inf 0x3f3f3f3f
  9. ///dfs1需要维护的:
  10. int sz[N];///记录以u为根节点的子树的节点的个数
  11. int dep[N];///当前节点的深度
  12. int fa[N];///当前节点的父节点
  13. int son[N];///存重儿子
  14. ///dfs2
  15. int top[N];///存当前节点所在的链的顶端节点
  16. int tid[N];///每个节点的新编号
  17. int val[N],val1[N];///val[]表示输入的值,val1表示更新节点后对应的值
  18. int clk;///新的编号++clk;
  19. struct node
  20. {
  21. int l,r,maxn,sum;
  22. }t[4*N];
  23. vector<int>g[N];
  24. void dfs1(int u,int f,int d)
  25. {
  26. dep[u]=d;
  27. fa[u]=f;
  28. sz[u]=1;
  29. for(int i=0;i<g[u].size();i++)
  30. {
  31. int v=g[u][i];
  32. if(v==f)
  33. continue;
  34. dfs1(v,u,d+1);
  35. sz[u]+=sz[v];///求以u为顶端节点的节点个数
  36. if(sz[v]>sz[son[u]])///如果v的size比现在有的u的重儿子的size还要大的话,,更新重儿子
  37. son[u]=v;
  38. }
  39. }
  40. void dfs2(int u,int f,int id)
  41. {
  42. top[u]=id;
  43. tid[u]=++clk;///对这棵树重新编号
  44. val1[clk]=val[u];///新的节点对应的val
  45. if(son[u]==0)///跑到叶子节点上了
  46. return;
  47. dfs2(son[u],u,id);
  48. for(int i=0;i<g[u].size();i++)
  49. {
  50. int v=g[u][i];
  51. if(v==f||v==son[u])
  52. continue;
  53. dfs2(v,u,v);
  54. }
  55. }
  56. ///建树
  57. void build(int id,int l,int r)
  58. {
  59. t[id].l=l;
  60. t[id].r=r;
  61. if(l==r)
  62. {
  63. t[id].maxn=t[id].sum=val1[l];
  64. return;
  65. }
  66. int mid=(l+r)/2;
  67. build(2*id,l,mid);
  68. build(2*id+1,mid+1,r);
  69. t[id].maxn=max(t[2*id].maxn,t[2*id+1].maxn);
  70. t[id].sum=t[2*id].sum+t[2*id+1].sum;
  71. }
  72. ///求最大值
  73. int qmax(int id,int l,int r)
  74. {
  75. if(t[id].l==l&&t[id].r==r)
  76. return t[id].maxn;
  77. int mid=(t[id].l+t[id].r)/2;
  78. if(r<=mid)
  79. return qmax(2*id,l,r);
  80. else if(l>mid)
  81. return qmax(2*id+1,l,r);
  82. else
  83. return max(qmax(2*id,l,mid),qmax(2*id+1,mid+1,r));
  84. }
  85. int getmax(int u,int v)
  86. {
  87. int ans=-inf;
  88. while(top[u]!=top[v])///要求的两个点不在同一条重链上
  89. {
  90. if(dep[top[u]]>dep[top[v]])///统一较深的为v
  91. swap(u,v);
  92. ans=max(ans,qmax(1,tid[top[v]],tid[v]));///查询v的顶端节点到v的最大值
  93. v=fa[top[v]];///跳到v的顶端节点的父节点上
  94. }
  95. if(dep[u]>dep[v])///在同一条重链上时,还是以v为较深的点
  96. swap(u,v);
  97. ans=max(ans,qmax(1,tid[u],tid[v]));///在同一条重链上查询最大值
  98. return ans;
  99. }
  100. ///求和
  101. int qsum(int id,int l,int r)
  102. {
  103. if(t[id].l==l&&t[id].r==r)
  104. return t[id].sum;
  105. int mid=(t[id].l+t[id].r)/2;
  106. if(r<=mid)
  107. return qsum(2*id,l,r);
  108. else if(l>mid)
  109. return qsum(2*id+1,l,r);
  110. else
  111. return qsum(2*id,l,mid)+qsum(2*id+1,mid+1,r);
  112. }
  113. int getsum(int u,int v)
  114. {
  115. int sum=0;
  116. while(top[u]!=top[v])
  117. {
  118. if(dep[top[u]]>dep[top[v]])
  119. swap(u,v);
  120. sum+=qsum(1,tid[top[v]],tid[v]);
  121. v=fa[top[v]];
  122. }
  123. if(dep[u]>dep[v])
  124. swap(u,v);
  125. sum+=qsum(1,tid[u],tid[v]);
  126. return sum;
  127. }
  128. ///权值更改
  129. void change(int id,int x,int num)
  130. {
  131. if(t[id].l==t[id].r)
  132. {
  133. t[id].maxn=t[id].sum=num;///把对应的权值改为新的权值
  134. return;
  135. }
  136. int mid=(t[id].l+t[id].r)/2;
  137. if(x<=mid)
  138. change(2*id,x,num);
  139. else if(x>mid)
  140. change(2*id+1,x,num);
  141. t[id].maxn=max(t[2*id].maxn,t[2*id+1].maxn);///改了之后要重新求一遍最大值和求和了
  142. t[id].sum=t[2*id].sum+t[2*id+1].sum;
  143. }
  144. int main()
  145. {
  146. int n;
  147. scanf("%d",&n);
  148. int a,b;
  149. for(int i=1;i<n;i++)
  150. {
  151. scanf("%d%d",&a,&b);
  152. g[a].push_back(b);
  153. g[b].push_back(a);
  154. }
  155. for(int i=1;i<=n;i++)
  156. scanf("%d",&val[i]);
  157. dfs1(1,0,1);
  158. dfs2(1,0,1);
  159. build(1,1,n);
  160. int m;
  161. char s[10];
  162. int x,y;
  163. scanf("%d",&m);
  164. for(int i=1;i<=m;i++)
  165. {
  166. scanf("%s%d%d",s,&x,&y);
  167. if(s[1]=='M')
  168. printf("%d\n",getmax(x,y));
  169. else if(s[1]=='S')
  170. printf("%d\n",getsum(x,y));
  171. else if(s[1]=='H')
  172. change(1,tid[x],y);
  173. }
  174. return 0;
  175. }

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注