题目描述
一棵树上有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：
4
1
2
2
10
6
5
6
5
16
说明
对于100％的数据，保证1<=n<=30000，0<=q<=200000；中途操作中保证每个节点的权值w在-30000到30000之间。
题解
先剖一下。
CHANGE：把dfn[x]处改为t
然后线段树同时维护两个值：mac（区间内最大值）和sum（区间和）
在修改的时候，先递归到叶子节点，然后在回溯的同时维护mac和sum，单次复杂度logn。
就星了。
/*
qwerta
P2590 [ZJOI2008]树的统计
Accepted
100
代码 C++，3.62KB
提交时间 2018-09-11 19:18:59
耗时/内存
3536ms, 6424KB
*/
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define R register
#define LL long long
inline int read()
{
char ch=getchar();
int x=;bool s=;
while(ch<''||ch>''){if(ch=='-')s=;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return s?x:-x;
}
const int MAXN=+;
struct emm{
int e,f;
}b[*MAXN];
int h[MAXN];
int tot=;
void con(int x,int y)
{
b[++tot].f=h[x];
h[x]=tot;
b[tot].e=y;
b[++tot].f=h[y];
h[y]=tot;
b[tot].e=x;
return;
}
int s;
int d[MAXN],fa[MAXN],top[MAXN],siz[MAXN],z[MAXN];
void dfs(int x)
{
siz[x]=,top[x]=x;
int mac=,macc=-;
for(int i=h[x];i;i=b[i].f)
if(!d[b[i].e])
{
d[b[i].e]=d[x]+;
fa[b[i].e]=x;
dfs(b[i].e);
siz[x]+=siz[b[i].e];
if(macc<siz[b[i].e]){mac=b[i].e,macc=siz[b[i].e];}
}
z[x]=mac;
top[mac]=x;
return;
}
int q[MAXN],dfn[MAXN];
void dfss(int x)
{
q[++tot]=x;
dfn[x]=tot;
if(z[x])dfss(z[x]);
for(int i=h[x];i;i=b[i].f)
if(fa[b[i].e]==x&&b[i].e!=z[x])
dfss(b[i].e);
return;
}
int fitop(int x)
{
if(top[x]==x)return x;
return top[x]=fitop(top[x]);
}
int val[MAXN];
struct ahh{
int l,r,mid,mac;
long long sum;
}a[*MAXN];
#define lz (i<<1)
#define rz ((i<<1)|1)
#define md a[i].mid
void build(int i,int ll,int rr)
{
a[i].l=ll;
a[i].r=rr;
if(ll==rr){a[i].mac=a[i].sum=val[q[ll]];return;}
md=(ll+rr)>>;
build(lz,ll,md);
build(rz,md+,rr);
a[i].mac=max(a[lz].mac,a[rz].mac);
a[i].sum=a[lz].sum+a[rz].sum;
return;
}
void change(int i,int x,int k)
{
if(a[i].l==a[i].r){a[i].mac=a[i].sum=k;return;}
if(x<=md)change(lz,x,k);
else change(rz,x,k);
a[i].mac=max(a[lz].mac,a[rz].mac);
a[i].sum=a[lz].sum+a[rz].sum;
return;
}
long long ans;
void findmac(int i,int ll,int rr)
{
if(a[i].l==ll&&a[i].r==rr){if(a[i].mac>ans)ans=a[i].mac;return;}
if(rr<=md)findmac(lz,ll,rr);
else if(md+<=ll)findmac(rz,ll,rr);
else {findmac(lz,ll,md);findmac(rz,md+,rr);}
return;
}
void findsum(int i,int ll,int rr)
{
if(a[i].l==ll&&a[i].r==rr){ans+=a[i].sum;return;}
if(rr<=md)findsum(lz,ll,rr);
else if(md+<=ll)findsum(rz,ll,rr);
else {findsum(lz,ll,md);findsum(rz,md+,rr);}
return;
}
int main()
{
//freopen("a.in","r",stdin);
int n;
cin>>n;
for(int i=;i<n;++i)
{
int u,v;
cin>>u>>v;
con(u,v);
}
s=min(,n);
d[s]=;
dfs(s);
tot=;
dfss(s);
for(int i=;i<=n;++i)
top[i]=fitop(i);
for(int i=;i<=n;++i)
cin>>val[i];
build(,,n);
int q;
cin>>q;
for(int i=;i<=q;++i)
{
string st;
cin>>st;
if(st[]=='C')
{
int u,t;
cin>>u>>t;
change(,dfn[u],t);
}
else if(st[]=='M')
{
int u,v;
cin>>u>>v;
ans=-;
while(top[u]!=top[v])
{
if(d[top[u]]<d[top[v]])swap(u,v);
findmac(,dfn[top[u]],dfn[u]);
u=fa[top[u]];
}
if(d[u]<d[v])swap(u,v);
findmac(,dfn[v],dfn[u]);
cout<<ans<<endl;
}
else
{
int u,v;
cin>>u>>v;
ans=;
while(top[u]!=top[v])
{
if(d[top[u]]<d[top[v]])swap(u,v);
findsum(,dfn[top[u]],dfn[u]);
u=fa[top[u]];
}
if(d[u]<d[v])swap(u,v);
findsum(,dfn[v],dfn[u]);
cout<<ans<<endl;
}
}
return ;
}