Bzoj 1036: [ZJOI2008]树的统计Count 树链剖分,LCT

1036: [ZJOI2008]树的统计Count

Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 11102 Solved: 4490
[Submit][Status][Discuss]

Description

一棵树上有n个节点，编号分别为1到n，每个节点都有一个权值w。我们将以下面的形式来要求你对这棵树完成一些操作： I. CHANGE u t : 把结点u的权值改为t II. QMAX u v: 询问从点u到点v的路径上的节点的最大权值 III. 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

HINT

Source

题解：

树链剖分或LCT模版题。

我写了个树剖：

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 #define lson k*2,l,mid
  4 #define rson k*2+1,mid+1,r
  5 #define MAXN 30010
  6 #define INF 1e9
  7 struct node
  8 {
  9     int begin,end,next;
 10 }edge[MAXN*2];
 11 struct NODE
 12 {
 13     int left,right,sum,mx,val;
 14 }tree[5*MAXN];
 15 int cnt,Head[MAXN],val[MAXN],deep[MAXN],size[MAXN],P[MAXN][15],belong[MAXN],pos[MAXN],SIZE,n;
 16 bool vis[MAXN];
 17 void addedge(int bb,int ee)
 18 {
 19     edge[++cnt].begin=bb;edge[cnt].end=ee;edge[cnt].next=Head[bb];Head[bb]=cnt;
 20 }
 21 void addedge1(int bb,int ee)
 22 {
 23     addedge(bb,ee);addedge(ee,bb);
 24 }
 25 int read()
 26 {
 27     int s=0,fh=1;char ch=getchar();
 28     while(ch<'0'||ch>'9'){if(ch=='-')fh=-1;ch=getchar();}
 29     while(ch>='0'&&ch<='9'){s=s*10+(ch-'0');ch=getchar();}
 30     return s*fh;
 31 }
 32 void dfs1(int u)
 33 {
 34     int i,v;
 35     size[u]=1;vis[u]=true;
 36     for(i=Head[u];i!=-1;i=edge[i].next)
 37     {
 38         v=edge[i].end;
 39         if(vis[v]==false)
 40         {
 41             deep[v]=deep[u]+1;
 42             P[v][0]=u;
 43             dfs1(v);
 44             size[u]+=size[v];
 45         }
 46     }
 47 }
 48 void Ycl()
 49 {
 50     int i,j;
 51     for(j=1;(1<<j)<=n;j++)
 52     {
 53         for(i=1;i<=n;i++)
 54         {
 55             if(P[i][j-1]!=-1)P[i][j]=P[P[i][j-1]][j-1];
 56         }
 57     }
 58 }
 59 void dfs2(int u,int chain)
 60 {
 61     int k=0,i,v;
 62     pos[u]=++SIZE;belong[u]=chain;
 63     for(i=Head[u];i!=-1;i=edge[i].next)
 64     {
 65         v=edge[i].end;
 66         if(deep[v]>deep[u]&&size[v]>size[k])k=v;
 67     }
 68     if(k==0)return;
 69     dfs2(k,chain);
 70     for(i=Head[u];i!=-1;i=edge[i].next)
 71     {
 72         v=edge[i].end;
 73         if(deep[v]>deep[u]&&v!=k)dfs2(v,v);
 74     }
 75 }
 76 int LCA(int x,int y)
 77 {
 78     int i,j;
 79     if(deep[x]<deep[y])swap(x,y);
 80     for(i=0;(1<<i)<=deep[x];i++);i--;
 81     for(j=i;j>=0;j--)if(deep[x]-(1<<j)>=deep[y])x=P[x][j];
 82     if(x==y)return x;
 83     for(j=i;j>=0;j--)
 84     {
 85         if(P[x][j]!=-1&&P[x][j]!=P[y][j])
 86         {
 87             x=P[x][j];
 88             y=P[y][j];
 89         }
 90     }
 91     return P[x][0];
 92 }
 93 void Pushup(int k)
 94 {
 95     tree[k].sum=tree[k*2].sum+tree[k*2+1].sum;
 96     tree[k].mx=max(tree[k*2].mx,tree[k*2+1].mx);
 97 }
 98 void Build(int k,int l,int r)
 99 {
100     tree[k].left=l;tree[k].right=r;
101     if(l==r)return;
102     int mid=(l+r)/2;
103     Build(lson);
104     Build(rson);
105 }
106 void Change(int k,int P,int V)
107 {
108     if(tree[k].left==tree[k].right)
109     {
110         tree[k].val=tree[k].sum=tree[k].mx=V;
111         return;
112     }
113     int mid=(tree[k].left+tree[k].right)/2;
114     if(P<=mid)Change(k*2,P,V);
115     else Change(k*2+1,P,V);
116     Pushup(k);
117 }
118 int Query_max(int k,int l,int r)
119 {
120     if(l<=tree[k].left&&tree[k].right<=r)return tree[k].mx;
121     int mid=(tree[k].left+tree[k].right)/2;
122     if(r<=mid)return Query_max(k*2,l,r);
123     else if(l>mid)return Query_max(k*2+1,l,r);
124     else return max(Query_max(k*2,l,mid),Query_max(k*2+1,mid+1,r));
125 }
126 int Query_sum(int k,int l,int r)
127 {
128     if(l<=tree[k].left&&tree[k].right<=r)return tree[k].sum;
129     int mid=(tree[k].left+tree[k].right)/2;
130     if(r<=mid)return Query_sum(k*2,l,r);
131     else if(l>mid)return Query_sum(k*2+1,l,r);
132     else return Query_sum(k*2,l,mid)+Query_sum(k*2+1,mid+1,r);
133 }
134 int solve_max(int x,int f)
135 {
136     int MAX=-INF;
137     while(belong[x]!=belong[f])
138     {
139         MAX=max(MAX,Query_max(1,pos[belong[x]],pos[x]));
140         x=P[belong[x]][0];
141     }
142     MAX=max(MAX,Query_max(1,pos[f],pos[x]));
143     return MAX;
144 }
145 int solve_sum(int x,int f)
146 {
147     int SUM=0;
148     while(belong[x]!=belong[f])
149     {
150         SUM+=Query_sum(1,pos[belong[x]],pos[x]);
151         x=P[belong[x]][0];
152     }
153     SUM+=Query_sum(1,pos[f],pos[x]);
154     return SUM;
155 }
156 int main()
157 {
158     freopen("bzoj_1036.in","r",stdin);
159     freopen("bzoj_1036.out","w",stdout);
160     int m,i,bb,ee,u,v,t,lca;
161     char zs[8];
162     n=read();
163     memset(Head,-1,sizeof(Head));cnt=1;
164     for(i=1;i<n;i++)
165     {
166         bb=read();ee=read();addedge1(bb,ee);
167     }
168     memset(P,-1,sizeof(P));SIZE=0;
169     dfs1(1);Ycl();
170     dfs2(1,1);
171     for(i=1;i<=n;i++)val[i]=read();
172     Build(1,1,n);
173     for(i=1;i<=n;i++)Change(1,pos[i],val[i]);
174     m=read();
175     for(i=1;i<=m;i++)
176     {
177         scanf("
%s",zs);
178         if(zs[0]=='C'){u=read();t=read();val[u]=t;Change(1,pos[u],val[u]);}
179         else
180         {
181             if(zs[1]=='M')
182             {
183                 u=read();v=read();
184                 lca=LCA(u,v);
185                 printf("%d
",max(solve_max(u,lca),solve_max(v,lca)));
186             }
187             else {u=read();v=read();lca=LCA(u,v);printf("%d
",solve_sum(u,lca)+solve_sum(v,lca)-val[lca]);}
188         }
189     }
190     fclose(stdin);
191     fclose(stdout);
192     return 0;
193 }