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

树的统计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. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注