「ZJOI2008」「LuoguP2590」树的统计（树链剖分

题目描述

一棵树上有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本身

输入输出格式

输入格式：

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

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

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

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

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

输出格式：

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

输入输出样例

输入样例#1： 复制

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

输出样例#1： 复制

说明

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

题解

先剖一下。

CHANGE：把dfn[x]处改为t

然后线段树同时维护两个值：mac（区间内最大值）和sum（区间和）

在修改的时候，先递归到叶子节点，然后在回溯的同时维护mac和sum，单次复杂度logn。

就星了。

  1 /*
  2     qwerta
  3     P2590 [ZJOI2008]树的统计
  4     Accepted
  5     100
  6     代码 C++，3.62KB
  7     提交时间 2018-09-11 19:18:59
  8     耗时/内存
  9     3536ms, 6424KB
 10 */
 11 #include<cmath>
 12 #include<cstdio>
 13 #include<iostream>
 14 #include<algorithm>
 15 using namespace std;
 16 #define R register
 17 #define LL long long
 18 inline int read()
 19 {
 20     char ch=getchar();
 21     int x=0;bool s=1;
 22     while(ch<'0'||ch>'9'){if(ch=='-')s=0;ch=getchar();}
 23     while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
 24     return s?x:-x;
 25 }
 26 const int MAXN=30000+7;
 27 struct emm{
 28     int e,f;
 29 }b[2*MAXN];
 30 int h[MAXN];
 31 int tot=0;
 32 void con(int x,int y)
 33 {
 34     b[++tot].f=h[x];
 35     h[x]=tot;
 36     b[tot].e=y;
 37     b[++tot].f=h[y];
 38     h[y]=tot;
 39     b[tot].e=x;
 40     return;
 41 }
 42 int s;
 43 int d[MAXN],fa[MAXN],top[MAXN],siz[MAXN],z[MAXN];
 44 void dfs(int x)
 45 {
 46     siz[x]=1,top[x]=x;
 47     int mac=0,macc=-1;
 48     for(int i=h[x];i;i=b[i].f)
 49     if(!d[b[i].e])
 50     {
 51         d[b[i].e]=d[x]+1;
 52         fa[b[i].e]=x;
 53         dfs(b[i].e);
 54         siz[x]+=siz[b[i].e];
 55         if(macc<siz[b[i].e]){mac=b[i].e,macc=siz[b[i].e];}
 56     }
 57     z[x]=mac;
 58     top[mac]=x;
 59     return;
 60 }
 61 int q[MAXN],dfn[MAXN];
 62 void dfss(int x)
 63 {
 64     q[++tot]=x;
 65     dfn[x]=tot;
 66     if(z[x])dfss(z[x]);
 67     for(int i=h[x];i;i=b[i].f)
 68     if(fa[b[i].e]==x&&b[i].e!=z[x])
 69     dfss(b[i].e);
 70     return;
 71 }
 72 int fitop(int x)
 73 {
 74     if(top[x]==x)return x;
 75     return top[x]=fitop(top[x]);
 76 }
 77 int val[MAXN];
 78 struct ahh{
 79     int l,r,mid,mac;
 80     long long sum;
 81 }a[8*MAXN];
 82 #define lz (i<<1)
 83 #define rz ((i<<1)|1)
 84 #define md a[i].mid
 85 void build(int i,int ll,int rr)
 86 {
 87     a[i].l=ll;
 88     a[i].r=rr;
 89     if(ll==rr){a[i].mac=a[i].sum=val[q[ll]];return;}
 90     md=(ll+rr)>>1;
 91     build(lz,ll,md);
 92     build(rz,md+1,rr);
 93     a[i].mac=max(a[lz].mac,a[rz].mac);
 94     a[i].sum=a[lz].sum+a[rz].sum;
 95     return;
 96 }
 97 void change(int i,int x,int k)
 98 {
 99     if(a[i].l==a[i].r){a[i].mac=a[i].sum=k;return;}
100     if(x<=md)change(lz,x,k);
101     else change(rz,x,k);
102     a[i].mac=max(a[lz].mac,a[rz].mac);
103     a[i].sum=a[lz].sum+a[rz].sum;
104     return;
105 }
106 long long ans;
107 void findmac(int i,int ll,int rr)
108 {
109     if(a[i].l==ll&&a[i].r==rr){if(a[i].mac>ans)ans=a[i].mac;return;}
110     if(rr<=md)findmac(lz,ll,rr);
111     else if(md+1<=ll)findmac(rz,ll,rr);
112     else {findmac(lz,ll,md);findmac(rz,md+1,rr);}
113     return;
114 }
115 void findsum(int i,int ll,int rr)
116 {
117     if(a[i].l==ll&&a[i].r==rr){ans+=a[i].sum;return;}
118     if(rr<=md)findsum(lz,ll,rr);
119     else if(md+1<=ll)findsum(rz,ll,rr);
120     else {findsum(lz,ll,md);findsum(rz,md+1,rr);}
121     return;
122 }
123 int main()
124 {
125     //freopen("a.in","r",stdin);
126     int n;
127     cin>>n;
128     for(int i=1;i<n;++i)
129     {
130         int u,v;
131         cin>>u>>v;
132         con(u,v);
133     }
134     s=min(7,n);
135     d[s]=1;
136     dfs(s);
137     tot=0;
138     dfss(s);
139     for(int i=1;i<=n;++i)
140     top[i]=fitop(i);
141     for(int i=1;i<=n;++i)
142     cin>>val[i];
143     build(1,1,n);
144     int q;
145     cin>>q;
146     for(int i=1;i<=q;++i)
147     {
148         string st;
149         cin>>st;
150         if(st[0]=='C')
151         {
152             int u,t;
153             cin>>u>>t;
154             change(1,dfn[u],t);
155         }
156         else if(st[1]=='M')
157         {
158             int u,v;
159             cin>>u>>v;
160             ans=-99999999999999;
161             while(top[u]!=top[v])
162             {
163                 if(d[top[u]]<d[top[v]])swap(u,v);
164                 findmac(1,dfn[top[u]],dfn[u]);
165                 u=fa[top[u]];
166             }
167             if(d[u]<d[v])swap(u,v);
168             findmac(1,dfn[v],dfn[u]);
169             cout<<ans<<endl;
170         }
171         else
172         {
173             int u,v;
174             cin>>u>>v;
175             ans=0;
176             while(top[u]!=top[v])
177             {
178                 if(d[top[u]]<d[top[v]])swap(u,v);
179                 findsum(1,dfn[top[u]],dfn[u]);
180                 u=fa[top[u]];
181             }
182             if(d[u]<d[v])swap(u,v);
183             findsum(1,dfn[v],dfn[u]);
184             cout<<ans<<endl;
185         }
186     }
187     return 0;
188 }