[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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

样例输出 #1

4
1
2
2
10
6
5
6
5
16
1
2
3
4
5
6
7
8
9
10

提示

对于 $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
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138