1036. [ZJOI2008]树的统计【树链剖分】

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

树链剖分模板

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstdlib>
  4 #include<cstring>
  5 using namespace std;
  6 
  7 int head[30001],num_edge;
  8 int Father[30001],Weight[30001];
  9 int Son[30001],Top[30001];
 10 int T_NUM[30001],a[30001];
 11 int Depth[30001];
 12 int sum,n,INF,ans;
 13 int TREE[30001];
 14 char st[101];
 15 struct node
 16 {
 17     int to,next;
 18 } edge[60005];
 19 struct node1
 20 {
 21     int max,sum;
 22 } Segt[120001];
 23 void add(int u,int v)
 24 {
 25     edge[++num_edge].to=v;
 26     edge[num_edge].next=head[u];
 27     head[u]=num_edge;
 28 }
 29 void dfs1(int x)
 30 {
 31     Weight[x]=1;
 32     Depth[x]=Depth[Father[x]]+1;
 33     for (int i=head[x]; i!=0; i=edge[i].next)
 34         if (edge[i].to!=Father[x])
 35         {
 36             Father[edge[i].to]=x;
 37             dfs1(edge[i].to);
 38             Weight[x]+=Weight[edge[i].to];
 39             if (Son[x]==0 || Weight[edge[i].to]>Weight[Son[x]])
 40                 Son[x]=edge[i].to;
 41         }
 42 }
 43 
 44 void dfs2(int x,int tp)
 45 {
 46     T_NUM[x]=++sum;
 47     TREE[sum]=a[x];
 48     Top[x]=tp;
 49     if (Son[x]!=0)
 50         dfs2(Son[x],tp);
 51     for (int i=head[x]; i!=0; i=edge[i].next)
 52         if (edge[i].to!=Son[x] && edge[i].to!=Father[x])
 53             dfs2(edge[i].to,edge[i].to);
 54 }
 55 
 56 void Build(int node,int l,int r,int a[])
 57 {
 58     if (l==r)
 59         Segt[node].max=Segt[node].sum=a[l];
 60     else
 61     {
 62         int mid=(l+r)/2;
 63         Build(node*2,l,mid,a);
 64         Build(node*2+1,mid+1,r,a);
 65         Segt[node].max=max(Segt[node*2].max,Segt[node*2+1].max);
 66         Segt[node].sum=Segt[node*2].sum+Segt[node*2+1].sum;
 67     }
 68 }
 69 
 70 void Update(int node,int l,int r,int x,int k)
 71 {
 72     if (l==r)
 73         Segt[node].max=Segt[node].sum=k;
 74     else
 75     {
 76         mid=(l+r)/2;
 77         (x<=mid)
 78         date(node*2,l,mid,x,k);
 79         else
 80             Update(node*2+1,mid+1,r,x,k);
 81         Segt[node].max=max(Segt[node*2].max,Segt[node*2+1].max);
 82         Segt[node].sum=Segt[node*2].sum+Segt[node*2+1].sum;
 83     }
 84 }
 85 
 86 int QueryMax(int node,int l,int r,int l1,int r1)
 87 {
 88     if (r<l1 || l>r1)
 89         return -INF;
 90     if (l1<=l && r<=r1)
 91         return Segt[node].max;
 92     int mid=(l+r)/2;
 93     return max(QueryMax(node*2,l,mid,l1,r1),
 94                QueryMax(node*2+1,mid+1,r,l1,r1));
 95 }
 96 
 97 int QuerySum(int node,int l,int r,int l1,int r1)
 98 {
 99     if (r<l1 || l>r1)
100         return 0;
101     if (l1<=l && r<=r1)
102         return Segt[node].sum;
103     int mid=(l+r)/2;
104     return QuerySum(node*2,l,mid,l1,r1)+
105            QuerySum(node*2+1,mid+1,r,l1,r1);
106 }
107 
108 int GetSum(int x,int y)
109 {
110     int fx,fy;
111     memset(&ans,0,sizeof(ans));
112     fx=Top[x];
113     fy=Top[y];
114     while (fx!=fy)
115     {
116         if (Depth[fx]<Depth[fy])
117             swap(fx,fy),swap(x,y);
118         ans+=QuerySum(1,1,n,T_NUM[fx],T_NUM[x]);
119         x=Father[fx],fx=Top[x];
120     }
121     if (Depth[x]>Depth[y]) swap(x,y);
122     return ans+=QuerySum(1,1,n,T_NUM[x],T_NUM[y]);
123 }
124 
125 int GetMax(int x,int y)
126 {
127     int fy,fx;
128     memset(&ans,-0x7f,sizeof(ans));
129     fx=Top[x];
130     fy=Top[y];
131     while (fx!=fy)
132     {
133         if (Depth[fx]<Depth[fy])
134             swap(fx,fy),swap(x,y);
135         ans=max(ans,QueryMax(1,1,n,T_NUM[fx],T_NUM[x]));
136         x=Father[fx],fx=Top[x];
137     }
138     if (Depth[x]>Depth[y]) swap(x,y);
139     return max(ans,QueryMax(1,1,n,T_NUM[x],T_NUM[y]));
140 }
141 
142 int main()
143 {
144     int i,u,v,l,m,x,y;
145     memset(&INF,0x7f,sizeof(INF));
146     scanf("%d",&n);
147     for (i=1; i<=n-1; ++i)
148     {
149         scanf("%d%d",&u,&v);
150         add(u,v);
151         add(v,u);
152     }
153     for (int i=1; i<=n; ++i)
154         scanf("%d",&a[i]);
155     Depth[1]=1;
156     dfs1(1);
157     dfs2(1,1);//两边预处理
158     Build(1,1,n,TREE);//TREE数组保存用来建线段树的区间
159     scanf("%d",&m);
160     for (int i=1; i<=m; ++i)
161     {
162         scanf("%s%d%d",&st,&x,&y);
163         if (st[1]=='H')
164             Update(1,1,n,T_NUM[x],y);
165         if (st[1]=='M')
166             printf("%d
",GetMax(x,y));
167         if (st[1]=='S')
168             printf("%d
",GetSum(x,y));
169     }
170 }