# Tree chain segmentation (Application of line tree)

### [Title Description]

Original title: ZJOI 2008

There are n nodes in a tree with numbers from 1 to N, and each node has a weight w. We will ask you to do something about this tree in the following form:

1.CHANGE u t: change the weight of node u to t;

2.QMAX u v: the maximum weight of nodes on the path from query point u to point v;

3.QSUM u v: the weight sum of nodes on the path from query point u to point v.

Note: nodes on the path from point u to point v include u and V itself.

#### [input]

The first line is a number n, indicating the number of nodes;

Next n − 1 lines, each line has two integers a and b, indicating that there is an edge between node A and node b;

Next n lines, an integer in each line, the integer wi in line I represents the weight of node i;

The next line, an integer q, represents the total number of operations;

Next, line q, one operation per line, is given in the form of CHANGE u t or QMAX u v or QSUM u v.

#### [output]

For each QMAX or QSUM operation, an integer is output per line to represent the required result.

```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
```

```4
1
2
2
10
6
5
6
5
16
```

#### [hint]

Data range and tips:

For 100% data, there are 1 ≤ n ≤ 3 × 104, 0 ≤ q ≤ 2 × 105. In the midway operation, the weight w of each node is guaranteed to be between − 30000 and 30000.

```#include<bits/stdc++.h>//The procedure explained by xyc
#define lc (k<<1)
#define rc (k<<1|1)
#define mid ((a[k].l+a[k].r)>>1)
using namespace std;
inline void in(int &x){
int f=1;x=0;char w=getchar();
while(w<'0'||w>'9'){if(w=='-') f=-f;w=getchar();}
while(w>='0'&&w<='9'){x=(x<<3)+(x<<1)+(w^48);w=getchar();}
x*=f;
}
const int N=3e4+10;
struct node{
int son,fa,deep,size,top,zhi,id;
}p[N];
struct tree{
int l,r,val,maxn;
}a[N<<2];
int n,m,x,y,tot,cnt;char op[100];
int fir[N],vis[N],rk[N],nxt[N<<1],ver[N<<1];
void dfs1(int x){
vis[x]=1,p[x].size=1,p[x].deep=p[p[x].fa].deep+1;int maxn=0;
for(int i=fir[x];i;i=nxt[i]){
int y=ver[i];if(vis[y]) continue;
p[y].fa=x,dfs1(y);p[x].size+=p[y].size;
if(p[y].size>maxn) maxn=p[y].size,p[x].son=y;
}
}
void dfs2(int x){
p[x].id=++cnt,rk[cnt]=x,p[x].top=x==p[p[x].fa].son?p[p[x].fa].top:x;
if(!p[x].son) return ;dfs2(p[x].son);
for(int i=fir[x];i;i=nxt[i]) {int y=ver[i];if(!p[y].id) dfs2(y);}
}
void build(int k,int l,int r){
a[k].l=l,a[k].r=r;
if(l==r) {a[k].maxn=a[k].val=p[rk[l]].zhi;return;}
build(lc,l,mid),build(rc,mid+1,r);
a[k].maxn=max(a[lc].maxn,a[rc].maxn);
a[k].val=a[lc].val+a[rc].val;
}
if(a[k].l==a[k].r){a[k].maxn=a[k].val=z;return;}
a[k].maxn=max(a[lc].maxn,a[rc].maxn);
a[k].val=a[lc].val+a[rc].val;
}
if(a[k].l>=l&&a[k].r<=r)return a[k].val;
int ans=0;
return ans;
}
if(a[k].l>=l&&a[k].r<=r)return a[k].maxn;
int ans=-N;
return ans;
}
int main(){
for(int i=1;i<=n;i++) in(p[i].zhi);
dfs1(1),dfs2(1),build(1,1,n),in(m);
for(int i=1;i<=m;i++){
scanf("%s",op),in(x),in(y);
if(op[3]=='X'){
int ans=-N;
while(p[x].top!=p[y].top)
if(p[p[x].top].deep>p[p[y].top].deep)
printf("%d\n",ans);
}
else if(op[3]=='M'){
int ans=0;
while(p[x].top!=p[y].top)
if(p[p[x].top].deep>p[p[y].top].deep)
printf("%d\n",ans);
}
}
return 0;
}
```
```#include<cstdio>//Another big guy's annotating program
#include<cstring>
using namespace std;
const int N=31000;
const int M=124000;
int n,q,k=1,first[N],summ,maxmax;
struct Edge{ int v,next;}edge[M];
int num[N];
int father[N],dep[N],size[N],son[N],top[N],seg[N],rev[N];
int maxn[M],sum[M];

int s=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){ s=(s<<3)+(s<<1)+ch-48;ch=getchar();}
return f*s;
}
edge[++k].v=vi;edge[k].next=first[ui];first[ui]=k;
edge[++k].v=ui;edge[k].next=first[vi];first[vi]=k;
}
void dfs1(int u,int fa){      //First time dfs
size[u]=1;          //u has 1 nodes, including itself
father[u]=fa;       //u's father is fa
dep[u]=dep[fa]+1;   //The depth of u is the depth of its father fa + 1
for(int i=first[u];i;i=edge[i].next){   //Exhaustion and all sides at the beginning of u
int v1=edge[i].v;
if(v1==fa) continue;
dfs1(v1,u);
size[u]+=size[v1];     //The number of nodes contained in u adds up the nodes of the son v1
if(size[v1]>size[son[u]])   //If the node number of v1 is more than the node number of son[u] of U
son[u]=v1;      //Renew my son
}
}
void dfs2(int u,int fa){      //Second times dfs
if(son[u]){   //Take the heavy son first to ensure that the position of the heavy path on the line tree is continuous
seg[son[u]]=++seg[0];    //The number of son[u] on the line tree is + + seg[0]
top[son[u]]=top[u];      //The top node of the heavy path of son[u] is the top node of his father U
rev[seg[0]]=son[u];      //The node number of seg[0] on the line tree is son[u]
dfs2(son[u],u);
}
for(int i=first[u];i;i=edge[i].next){
int v1=edge[i].v;
if(top[v1]) continue;   //If v1 has been accessed, i.e. a son or father, no further access is required
seg[v1]=++seg[0];
rev[seg[0]]=v1;
top[v1]=v1;    //If (u,v1) is a light edge, v1 is the top node of its heavy path
dfs2(v1,u);
}
}
int max(int x,int y){ if(x>y) return x;return y;}
void build(int k,int l,int r){  //Building line tree
int mid=(l+r)>>1;
if(l==r){
maxn[k]=sum[k]=num[rev[l]];
return;
}
build(k<<1,l,mid);
build((k<<1)+1,mid+1,r);
sum[k]=sum[k<<1]+sum[(k<<1)+1];
maxn[k]=max(maxn[k<<1],maxn[(k<<1)+1]);
}
void change(int k,int l,int r,int val,int pos){  //Modify pos node to val
if(pos<l||r<pos) return;   //If not, exit
if(l==r&&l==pos){    //If points are found, change
sum[k]=val;
maxn[k]=val;
return;
}
int mid=(l+r)>>1;
if(mid>=pos) change(k<<1,l,mid,val,pos);
if(mid<pos) change((k<<1)+1,mid+1,r,val,pos);
sum[k]=sum[k<<1]+sum[(k<<1)+1];
maxn[k]=max(maxn[k<<1],maxn[(k<<1)+1]);
}
void swap(int &x,int &y){ int temp=x;x=y;y=temp;}
void query(int k,int l,int r,int x,int y){
if(y<l||x>r) return;
if(x<=l&&r<=y){
summ+=sum[k];
maxmax=max(maxmax,maxn[k]);
return;
}
int mid=(l+r)>>1;
if(x<=mid) query(k<<1,l,mid,x,y);
if(mid<y) query((k<<1)+1,mid+1,r,x,y);
}
void ask(int x,int y){  //Path query
int fx=top[x],fy=top[y];  //Find the top nodes of the paths where xy is located
while(fx!=fy){       //xy is on the same path when exiting
if(dep[fx]<dep[fy]){   //Ensure greater depth of x
swap(x,y);swap(fx,fy);
}
query(1,1,seg[0],seg[fx],seg[x]);
x=father[fx];fx=top[x];
}
if(dep[x]>dep[y]) swap(x,y);    //Ensure that the number of x on the line tree is less than y
query(1,1,seg[0],seg[x],seg[y]);
}
int main(){
dfs1(1,0);
seg[0]=1;    //Record the number of the line tree up to now
seg[1]=1;    //The positions of root nodes 0 and 1 in the line segment tree are 1
top[1]=1;   //The top node of the path where 1 is located is 1
rev[1]=1;   //Is the node corresponding to the first position in the line tree 1
dfs2(1,0);
build(1,1,seg[0]);    //Building line tree
while(q--){
char st[10];
scanf("%s",st);
if(st[0]=='C')
change(1,1,seg[0],vi,seg[ui]);
else{
summ=0;
maxmax=-100000000;