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
分析：
为了练一下lct，就用lct搞了一下
不知道为什么这么慢
有一点要注意：
在读入每个节点的值的时候，也要像修改值那样
makeroot->update
不这样写的话就会出错
这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const ll N=60001;
ll pre[N],ch[N][2],sum[N],v[N],mx[N];
bool rev[N];
int q[N],n,m;
int get(int bh)
{
return ch[pre[bh]][0]==bh ? 0:1;
}
int isroot(int bh)
{
return ch[pre[bh]][0]!=bh&&ch[pre[bh]][1]!=bh;
}
inline void update(int bh)
{
if (bh)
{
sum[bh]=v[bh];
if (ch[bh][0]) sum[bh]+=sum[ch[bh][0]];
if (ch[bh][1]) sum[bh]+=sum[ch[bh][1]];
mx[bh]=v[bh];
if (ch[bh][0]) mx[bh]=max(mx[bh],mx[ch[bh][0]]);
if (ch[bh][1]) mx[bh]=max(mx[bh],mx[ch[bh][1]]);
}
}
inline void push(int bh)
{
if (bh&&rev[bh])
{
rev[bh]^=1;
rev[ch[bh][0]]^=1;
rev[ch[bh][1]]^=1;
swap(ch[bh][0],ch[bh][1]);
}
}
inline void rotate(int bh)
{
int fa=pre[bh];
int grand=pre[fa];
int wh=get(bh);
if (!isroot(fa)) ch[grand][ch[grand][0]==fa ? 0:1]=bh;
ch[fa][wh]=ch[bh][wh^1];
pre[ch[fa][wh]]=fa;
ch[bh][wh^1]=fa;
pre[fa]=bh;
pre[bh]=grand;
update(fa);
update(bh);
}
inline void splay(int bh)
{
int top=0;
q[++top]=bh;
for (int i=bh;!isroot(i);i=pre[i])
q[++top]=pre[i];
while (top)
push(q[top--]);
for (int fa;!isroot(bh);rotate(bh))
if (!isroot(fa=pre[bh]))
rotate(get(bh)==get(fa) ? fa:bh);
}
inline void expose(int bh)
{
int t=0;
while (bh)
{
splay(bh);
ch[bh][1]=t;
update(bh); ///
t=bh;
bh=pre[bh];
}
}
inline void makeroot(int bh)
{
expose(bh);
splay(bh);
rev[bh]^=1;
}
inline void cut(int x,int y)
{
makeroot(x);
expose(y);
splay(y);
ch[y][0]=pre[x]=0;
update(y);
update(x);
}
inline void link(int x,int y)
{
makeroot(x);
pre[x]=y;
update(x); ///
}
inline int find(int x)
{
expose(x);
splay(x);
int t=x;
while (ch[t][0]) t=ch[t][0];
return t;
}
int main()
{
scanf("%d",&n);
for (int i=1;i<n;i++)
{
int u,w;
scanf("%d%d",&u,&w);
link(u,w);
}
for (int i=1;i<=n;i++)
{
scanf("%lld",&v[i]); //也是一种程度上的修改
makeroot(i);
update(i); //update
}
char opt[10];
scanf("%d",&m);
scanf("%c",&opt[0]);
for (int i=1;i<=m;i++)
{
int u,w;
scanf("%s",&opt);
scanf("%d%d",&u,&w);
if (opt[1]=='M')
{
makeroot(u);
expose(w);
splay(w);
printf("%lld
",mx[w]);
}
else if (opt[1]=='S')
{
makeroot(u);
expose(w);
splay(w);
printf("%lld
",sum[w]);
}
else if (opt[0]=='C')
{
makeroot(u);
v[u]=(ll)w;
update(u);
}
scanf("%c",&opt[0]);
}
return 0;
}