C++之路进阶——codevs2460（树的统计）

2460 树的统计

 

2008年省队选拔赛浙江

 时间限制: 2 s
 空间限制: 128000 KB
 题目等级 : 大师 Master
 
 
 
题目描述 Description

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。

我们将以下面的形式来要求你对这棵树完成一些操作：

  1. I.                    CHANGE u t : 把结点u的权值改为t
  2. II.                 QMAX u v: 询问从点u到点v的路径上的节点的最大权值
  3. III.               QSUM u v: 询问从点u到点v的路径上的节点的权值和

 

注意：从点u到点v的路径上的节点包括u和v本身

输入描述 Input Description

输入文件的第一行为一个整数n，表示节点的个数。

       接下来n – 1行，每行2个整数a和b，表示节点a和节点b之间有一条边相连。

       接下来n行，每行一个整数，第i行的整数wi表示节点i的权值。

       接下来1行，为一个整数q，表示操作的总数。

接下来q行，每行一个操作，以“CHANGE u t”或者“QMAX u v”或者“QSUM u v”的形式给出。

输出描述 Output Description

       对于每个“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

数据范围及提示 Data Size & Hint

对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。

题解

     裸的树链剖分...

      

树链剖分就是把树拆成一系列链，然后用数据结构对链进行维护。

通常的剖分方法是轻重链剖分，所谓轻重链就是对于节点u的所有子结点v，size[v]最大的v与u的边是重边，其它边是轻边，其中size[v]是以v为根的子树的节点个数，全部由重边组成的路径是重路径，根据论文上的证明，任意一点到根的路径上存在不超过logn条轻边和logn条重路径。

这样我们考虑用数据结构来维护重路径上的查询，轻边直接查询。

通常用来维护的数据结构是线段树，splay较少见。

具体步骤

预处理

第一遍dfs求出树每个结点的深度deep[x]，其为根的子树大小size[x]

以及祖先的信息fa[x][i]表示x往上距离为2^i的祖先

第二遍dfs

ž根节点为起点，向下拓展构建重链

选择最大的一个子树的根继承当前重链

其余节点，都以该节点为起点向下重新拉一条重链

ž给每个结点分配一个位置编号，每条重链就相当于一段区间，用数据结构去维护。

把所有的重链首尾相接，放到同一个数据结构上，然后维护这一个整体即可

修改操作

ž1、单独修改一个点的权值

根据其编号直接在数据结构中修改就行了。

2、修改点u和点v的路径上的权值

（1）若u和v在同一条重链上

直接用数据结构修改pos[u]至pos[v]间的值。

（2）若u和v不在同一条重链上

一边进行修改，一边将u和v往同一条重链上靠，然后就变成了情况（1）。

查询操作

ž查询操作的分析过程同修改操作

题目不同，选用不同的数据结构来维护值，通常有线段树和splay

代码：

    树链剖分

  1 #include<cstdio>
  2 #include<iostream>
  3 #include<cstring>
  4 #define INF 0x7fffffff
  5 #define N 30005
  6 #define M 60005
  7 
  8 using namespace std;
  9 
 10 int n,q,cnt,sz;
 11 int fa[N][15],v[N],deep[N],size[N],head[N];
 12 int pos[N],belong[N];
 13 bool vis[N];
 14 struct node
 15     {
 16      int to;
 17      int next;
 18     }e[M];
 19     
 20 struct ss
 21      {
 22        int l;
 23        int r;
 24        int mx;
 25        int sum;
 26      }t[100005];
 27      
 28 void insert(int u,int v)
 29    {
 30     e[++cnt].to=v; e[cnt].next=head[u]; head[u]=cnt;
 31     e[++cnt].to=u; e[cnt].next=head[v]; head[v]=cnt;
 32    }
 33     
 34 void inint()
 35    {
 36      scanf("%d",&n);
 37      for (int i=1;i<n;i++)
 38         {
 39           int x,y;
 40           scanf("%d%d",&x,&y);
 41           insert(x,y);
 42         }
 43     for (int i=1;i<=n;i++) scanf("%d",&v[i]);
 44    }
 45    
 46 void getree(int x)
 47    {
 48      size[x]=1;
 49      vis[x]=1;
 50      for (int i=1;i<=14;i++)
 51         {
 52           if (deep[x]<(1<<i)) break;
 53           fa[x][i]=fa[fa[x][i-1]][i-1];
 54         }
 55     for (int i=head[x];i;i=e[i].next)
 56         {
 57           if (vis[e[i].to]) continue;
 58           deep[e[i].to]=deep[x]+1;
 59           fa[e[i].to][0]=x;
 60           getree(e[i].to);
 61           size[x]+=size[e[i].to];
 62         }
 63    }
 64    
 65 void dfs(int x,int chain)
 66    {
 67     int k=0; 
 68     sz++;
 69     pos[x]=sz;
 70     belong[x]=chain;
 71     for (int i=head[x];i;i=e[i].next)
 72         if (deep[e[i].to]>deep[x]&&size[e[i].to]>size[k])
 73            k=e[i].to;
 74     if (k==0) return;
 75     dfs(k,chain);
 76     for (int i=head[x];i;i=e[i].next)
 77        if (deep[e[i].to]>deep[x]&&k!=e[i].to)
 78            dfs(e[i].to,e[i].to);
 79    }
 80    
 81 int lca(int x,int y)
 82   {
 83     if (deep[x]<deep[y]) swap(x,y);
 84     int t=deep[x]-deep[y];
 85     for (int i=0;i<=14;i++)
 86        if ((1<<i)&t) x=fa[x][i];
 87     for (int i=14;i>=0;i--)
 88          if (fa[x][i]!=fa[y][i])
 89               {
 90                x=fa[x][i];
 91                y=fa[y][i];
 92               }
 93     if (x==y) return x;
 94      else return fa[x][0];
 95   } 
 96   
 97 void build(int k,int l,int r)
 98    {
 99      t[k].l=l;
100      t[k].r=r;
101      if (l==r) return;
102      int mid=(l+r)>>1;
103      build(k<<1,l,mid);
104      build(k<<1|1,mid+1,r);
105    }
106    
107 void change(int k,int x,int y)
108    {
109       int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
110       if (l==r)
111           {
112             t[k].sum=t[k].mx=y;
113             return;
114           }
115       if (x<=mid) change(k<<1,x,y);
116          else change(k<<1|1,x,y);
117       t[k].sum=t[k<<1].sum+t[k<<1|1].sum;
118       t[k].mx=max(t[k<<1].mx,t[k<<1|1].mx);
119    }
120    
121 int find_sum(int k,int x,int y)
122    {
123      int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
124       if (l==x&&y==r) return t[k].sum;
125       if (y<=mid) return find_sum(k<<1,x,y);
126          else if (x>mid) return find_sum(k<<1|1,x,y);
127                else return find_sum(k<<1,x,mid)+find_sum(k<<1|1,mid+1,y);
128    }
129    
130 int find_mx(int k,int x,int y)
131    {
132      int l=t[k].l,r=t[k].r,mid=(l+r)>>1;
133      if (l==x&&r==y) return t[k].mx;
134      if (y<=mid) return find_mx(k<<1,x,y);
135         else if (x>mid) return find_mx(k<<1|1,x,y);
136                else  return max(find_mx(k<<1,x,mid),find_mx(k<<1|1,mid+1,y));
137    }
138    
139 int solve_mx(int x,int f)
140    {
141       int mx=-INF;
142       while(belong[x]!=belong[f])
143          {
144            mx=max(mx,find_mx(1,pos[belong[x]],pos[x]));
145            x=fa[belong[x]][0];
146          }
147      mx=max(mx,find_mx(1,pos[f],pos[x]));
148      return mx;
149    }
150    
151 int solve_sum(int x,int f)
152    {
153     int sum=0;
154     while (belong[x]!=belong[f])
155        {
156          sum+=find_sum(1,pos[belong[x]],pos[x]);
157          x=fa[belong[x]][0];
158        }
159     sum+=find_sum(1,pos[f],pos[x]);
160     return sum;
161    }
162    
163 void solve()
164   {
165     build(1,1,n);
166     for (int i=1;i<=n;i++)
167       change(1,pos[i],v[i]);
168     scanf("%d",&q);
169     char ch[6];
170     for (int i=1;i<=q;i++)
171        {
172           int x,y;
173           scanf("%s%d%d",ch,&x,&y);
174           if (ch[0]=='C')
175               {
176                 v[x]=y;
177                 change(1,pos[x],y);
178               }
179              else
180               {
181                 int t=lca(x,y);
182                 if (ch[1]=='M')
183                    printf("%d
",max(solve_mx(x,t),solve_mx(y,t)));
184                  else 
185                    printf("%d
",solve_sum(x,t)+solve_sum(y,t)-v[t]);
186               }
187        }
188   }
189   
190 int main()
191   {
192     inint();
193     getree(1);
194     dfs(1,1);
195     solve();
196     return 0;
197   }

块状树：

 1 #include<bits/stdc++.h>
 2 #define maxn (int)1e5+10
 3 
 4 using namespace std;
 5 
 6 vector<int>g[maxn],ge[maxn];
 7 int cnt,sqrtn,n,m;
 8 int w[maxn],sum[maxn],mx[maxn],fa[maxn],deep[maxn],bel[maxn],size[maxn];
 9 
10 void dfs(int u) 
11    {
12     for(int i=0;i<g[u].size();i++)
13        {
14         int v=g[u][i];
15         if(v==fa[u])continue;
16         fa[v]=u;
17         deep[v]=deep[u]+1;
18         if(size[bel[u]]<sqrtn)
19          {
20             size[bel[u]]++;bel[v]=bel[u];
21             ge[u].push_back(v);
22         }
23         dfs(v);    
24     }
25 }
26    
27 void dfs(int u,int s,int maxx) 
28   {
29     s+=w[u];
30     sum[u]=s;
31     maxx=max(maxx,w[u]);
32     mx[u]=maxx;
33     for(int i=0;i<ge[u].size();i++)
34        dfs(ge[u][i],s,maxx);
35 }
36 
37 void change(int u,int ww)
38    {
39     w[u]=ww;
40     if(bel[u]==u) dfs(u,0,INT_MIN);
41     else dfs(u,sum[fa[u]],mx[fa[u]]);  
42 } 
43 
44 pair<int,int> qsumax(int u,int v)
45    { 
46     int s=0,maxx=INT_MIN;
47     while(u!=v){
48         if(deep[u]<deep[v])swap(u,v);
49         if(bel[u]==bel[v])
50           {
51             s+=w[u];maxx=max(maxx,w[u]);
52             u=fa[u];
53         }
54          else
55            {
56             if(deep[bel[u]]<deep[bel[v]])swap(u,v);
57             s+=sum[u],maxx=max(maxx,mx[u]);
58             u=fa[bel[u]];
59         }
60     }
61     s+=w[u],maxx=max(maxx,w[u]);
62     return pair<int,int>(s,maxx);
63 }
64     
65 int main()
66     {
67        scanf("%d",&n);    
68        sqrtn=sqrt(n);     
69        for (int i=1;i<n;i++)
70          {
71                int u,v;
72                scanf("%d%d",&u,&v);
73                g[u].push_back(v);
74               g[v].push_back(u);
75              }
76       for (int i=1;i<=n;i++)
77         scanf("%d",w+i),bel[i]=i,size[i]=1;
78       dfs(1);                  
79       int q;
80       for(int i=1;i<=n;i++)if(bel[i]==i)
81            dfs(i,0,INT_MIN);
82       scanf("%d",&q);
83       while (q--)
84         {
85           int x,y;    
86           char op[5];     
87           scanf("%s%d%d",op,&x,&y);    
88           if(op[0]=='C') change(x,y);
89             else
90             {
91               pair<int,int>anss=qsumax(x,y);
92               if(op[1]=='M')
93                      printf("%d
",anss.second);
94                else printf("%d
",anss.first);            
95                 }
96     }    
97       return 0;
98     }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/grhyxzc/p/5134397.html