[ZJOI2008]樹的統計(過程都在注釋)

題目描述

一棵樹上有 $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$ 個整數 $w_i$ 錶示節點 $i$ 的權值。

接下來 $1$ 行，為一個整數 $q$，錶示操作的總數。

接下來 $q$ 行，每行一個操作，以 CHANGE u t 或者 QMAX u v 或者 QSUM u v 的形式給出。

輸出格式

對於每個 QMAX 或者 QSUM 的操作，每行輸出一個整數錶示要求輸出的結果。

樣例 #1

樣例輸入 #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\le n\le 3\times 10^4$，$0\le q\le 2\times 10^5$。

中途操作中保證每個節點的權值 $w$ 在 $-3\times 10^4$ 到 $3\times 10^4$ 之間。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
typedef long long ll;
int head[N],cnt;
int fa[N],size[N],deep[N],son[N],top[N],dfsxu[N],id[N],k;
//fa[i] 節點i的父節點 size[i] 以i為根的子樹總節點數
//deep[i] 節點i的深度 son[i] 節點i的重兒子
//top[i] 節點i所在的重鏈的最頂上元素
//dfsxu dfs序 id 時間戳
int n,v[N];
struct stu{
    
    int sum,max;
}tree[N*4];
struct stuu{
    
	int to,nt;
}ed[N*2];
void add(int u,int v){
    //鏈式前向星加邊
	ed[cnt]=stuu{
    v,head[u]};
	head[u]=cnt++;
}
void dfs1(int u,int f){
    //u為當前節點,f為當前節點的父節點；初始化1
    fa[u]=f;//u節點的父節點是f
    deep[u]=deep[f]+1;//深度+1
    size[u]=1;
    int maxsize=-1;//判斷是不是重兒子的臨時變量
    for(int i=head[u];i!=-1;i=ed[i].nt){
    //遍曆所有兒子，不斷更新同時找到重兒子
		int v=ed[i].to;
        if(v==f) continue;//是父親肯定直接跳過
        dfs1(v,u);//深度遍曆,當前節點變為父節點，找到的兒子變為當前節點繼續遍曆下去
        size[u]+=size[v];//遍曆完成後，讓當前節點的大小加上兒子的大小
        if(size[v]>maxsize){
    //如果兒子的大小大於臨時變量
            maxsize=size[v];//就賦給臨時變量
            son[u]=v;//更改當前節點的重兒子
        }
    }
}
void dfs2(int u,int t){
    //初始化2
    id[u]=++k;//每到了一個節點賦時間戳
    top[u]=t;//節點u所在重鏈的頂端是t
    dfsxu[k]=u;//存好dfs序
    if(!son[u]) return;//沒有重兒子就沒兒子了直接返回
    dfs2(son[u],t);//繼續往重兒子走
    for(int i=head[u];i!=-1;i=ed[i].nt){
    
        int v =ed[i].to;
        if(v==fa[u]||v==son[u]) continue;//如果是父節點或重兒子直接跳過
        dfs2(v,v);//一些重鏈從輕兒子開始往下有,頂部是輕兒子
    }
}
void pushup(int u){
    //更新
    tree[u].sum=tree[u<<1].sum+tree[u<<1|1].sum;//左右兩子段的區間和相加反饋給頂部
    tree[u].max=max(tree[u<<1].max,tree[u<<1|1].max);
}
void build(int l,int r,int u){
    //建樹
	if(l==r){
    //到達葉子結點，更新並返回
		tree[u].sum=tree[u].max=v[dfsxu[l]];
		return ;
	}//否則這個結點代錶的不止一個點，它還有兩個兒子
	int mid=(l+r)>>1;
	build(l,mid,u<<1);//遞歸左子樹
	build(mid+1,r,u<<1|1);//遞歸右子樹
	pushup(u);//更新
}
void update(int l,int r,int u,int a,int b){
    
    if(l==r){
    //到達葉子結點，更新並返回
        tree[u].sum=tree[u].max=b;
        return ;
    }
    int mid=(l+r)>>1;
	if(a<=mid) update(l,mid,u<<1,a,b);//遞歸左子樹
	else update(mid+1,r,u<<1|1,a,b);//遞歸右子樹
	pushup(u);//更新
}
int querymax(int l,int r,int u,int ql,int qr){
    
    if(ql<=l&&r<=qr){
    //作為子區間被包含，則進行整體修改，不繼續深入
        return tree[u].max;
    }//否則處於交錯，則需要繼續深入更底層子區間
    int k=-N;
	int mid=(l+r)>>1;//折半查找
	if(ql<=mid) k=max(k,querymax(l,mid,u<<1,ql,qr));//詢問的一部分在左兒子的管轄範圍內
	if(qr>=mid+1) k=max(k,querymax(mid+1,r,u<<1|1,ql,qr));//一部分在右兒子範圍內
	return k;
}
int querysum(int l,int r,int u,int ql,int qr){
    
    if(ql<=l&&r<=qr){
    //作為子區間被包含，則進行整體修改，不繼續深入
        return tree[u].sum;
    }//否則處於交錯，則需要繼續深入更底層子區間
    int k=0;
	int mid=(l+r)>>1;//折半查找
	if(ql<=mid) k+=querysum(l,mid,u<<1,ql,qr);//詢問的一部分在左兒子的管轄範圍內
	if(qr>=mid+1) k+=querysum(mid+1,r,u<<1|1,ql,qr);//一部分在右兒子範圍內
	return k;
}
int getsum(int a,int b){
    
    int k=0;
    while(top[a]!=top[b]){
    //找LCA：當x,y不在同一條重鏈，比較x,y所在重鏈鏈首的深度大小
        if(deep[top[a]]<deep[top[b]]) swap(a,b);//確保較深
        k+=querysum(1,n,1,id[top[a]],id[a]);
        a=fa[top[a]];//較深的那個沿著重鏈跳到鏈首的父親處
    }
    if(deep[a]>deep[b]) swap(a,b);
    return k+querysum(1,n,1,id[a],id[b]);
}
int getmax(int a,int b){
    
    int k=-N;
    while(top[a]!=top[b]){
    //找LCA：當x,y不在同一條重鏈，比較x,y所在重鏈鏈首的深度大小
        if(deep[top[a]]<deep[top[b]]) swap(a,b);//確保較深
        k=max(k,querymax(1,n,1,id[top[a]],id[a]));
        a=fa[top[a]];//較深的那個沿著重鏈跳到鏈首的父親處
    }
    if(deep[a]>deep[b]) swap(a,b);
    return max(k,querymax(1,n,1,id[a],id[b]));
}
int main(){
    
    cin>>n;
    memset(head,-1,sizeof(head));
    for(int i=1;i<n;i++){
    
        int u,v;
        scanf("%d%d",&u,&v);
        add(u,v);
        add(v,u);
    }
    for(int i=1;i<=n;i++) scanf("%d",&v[i]);
    dfs1(1,0);
    dfs2(1,1);
    build(1,n,1);
    int qqq;
    cin>>qqq;
    while(qqq--){
    
        string qq;
        int u,t;
        cin>>qq>>u>>t;
        if(qq=="QMAX") cout<<getmax(u,t)<<endl;
        else if(qq=="QSUM") cout<<getsum(u,t)<<endl;
        else update(1,n,1,id[u],t);
    }
    return 0;
}