P2590[ZJOI2008]树的统计（zkw线段树版的树链剖分）

传送门

题目描述
一棵树上有 nn 个节点&＃xff0c;编号分别为 11 到 nn&＃xff0c;每个节点都有一个权值 ww。

我们将以下面的形式来要求你对这棵树完成一些操作&＃xff1a;

I. CHANGE u t : 把结点 uu 的权值改为 tt。

II. QMAX u v: 询问从点 uu 到点 vv 的路径上的节点的最大权值。

III. QSUM u v: 询问从点 uu 到点 vv 的路径上的节点的权值和。

注意&＃xff1a;从点 uu 到点 vv 的路径上的节点包括 uu 和 vv 本身。

输入格式
输入文件的第一行为一个整数 nn&＃xff0c;表示节点的个数。

接下来 n-1n−1 行&＃xff0c;每行 22 个整数 aa 和 bb&＃xff0c;表示节点 aa 和节点 bb 之间有一条边相连。

接下来一行 nn 个整数&＃xff0c;第 ii 个整数 w_iw
i
​
表示节点 ii 的权值。

接下来 11 行&＃xff0c;为一个整数 qq&＃xff0c;表示操作的总数。

接下来 qq 行&＃xff0c;每行一个操作&＃xff0c;以 CHANGE u t 或者 QMAX u v 或者 QSUM u v 的形式给出。

输出格式
对于每个 QMAX 或者 QSUM 的操作&＃xff0c;每行输出一个整数表示要求输出的结果。

输入输出样例
输入 #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 %100% 的数据&＃xff0c;保证 1\le n \le 3\times 10^41≤n≤3×10
4
&＃xff0c;0\le q\le 2\times 10^50≤q≤2×10
5
。

中途操作中保证每个节点的权值 ww 在 -3\times 10^4−3×10
4
到 3\times 10^43×10
4
之间。

树链剖分模板题&＃xff0c;用zkw线段树做的

#include
#define inf 0x7fffffff
#define ll long long
#define int long long
//#define double long double
#define eps 1e-8
//#define mod 1e9&＃43;7
using namespace std;
//const int mod&＃61;1e9&＃43;7;
const int M&＃61;1e7&＃43;5;
const int N&＃61;1e6&＃43;5;//?????????? 4e8
struct node
{int ver,next;
}e[N];
int tot,head[N];
int num;
int a[N],w[N],dfn[N],son[N],sz[N];
int dep[N],fa[N],top[N];
int tree1[N],tree2[N];
int n,m;
void add(int x,int y)
{e[&＃43;&＃43;tot].ver&＃61;y;e[tot].next&＃61;head[x];head[x]&＃61;tot;
}
void addedge(int x,int y)
{add(x,y),add(y,x);
}
void dfs1(int x,int pre)
{int maxn&＃61;-1;sz[x]&＃61;1,dep[x]&＃61;dep[pre]&＃43;1;fa[x]&＃61;pre;for(int i&＃61;head[x];i;i&＃61;e[i].next){int y&＃61;e[i].ver;if(y&＃61;&＃61;pre) continue;dfs1(y,x);sz[x]&＃43;&＃61;sz[y];if(sz[y]>maxn){maxn&＃61;sz[y];son[x]&＃61;y;} }
}
void dfs2(int x,int pre)
{dfn[x]&＃61;&＃43;&＃43;num;top[x]&＃61;pre;w[num]&＃61;a[x];if(!son[x]) return;dfs2(son[x],pre);for(int i&＃61;head[x];i;i&＃61;e[i].next){int y&＃61;e[i].ver;if(y&＃61;&＃61;fa[x]||y&＃61;&＃61;son[x]) continue;dfs2(y,y);}
}
void bulid()
{for(m&＃61;1;m<&＃61;n&＃43;1;m<<&＃61;1);for(int i&＃61;m&＃43;1;i<&＃61;m&＃43;n;i&＃43;&＃43;) tree1[i]&＃61;tree2[i]&＃61;w[i-m];for(int i&＃61;m-1;i;i--) tree1[i]&＃61;tree1[i<<1]&＃43;tree1[i<<1|1],tree2[i]&＃61;max(tree2[i<<1],tree2[i<<1|1]);
}
void change(int pos,int x)
{pos&＃43;&＃61;m;tree1[pos]&＃61;tree2[pos]&＃61;x;pos>>&＃61;1;for(int i&＃61;pos;i;i>>&＃61;1) tree1[i]&＃61;tree1[i<<1]&＃43;tree1[i<<1|1],tree2[i]&＃61;max(tree2[i<<1],tree2[i<<1|1]);
}
int ask(int f,int l,int r)
{int ans1&＃61;0,ans2&＃61;-1e9;for(l&＃61;l&＃43;m-1,r&＃61;r&＃43;m&＃43;1;l^r^1;l>>&＃61;1,r>>&＃61;1){if(~l&1) ans1&＃43;&＃61;tree1[l^1],ans2&＃61;max(ans2,tree2[l^1]);if(r&1) ans1&＃43;&＃61;tree1[r^1],ans2&＃61;max(ans2,tree2[r^1]);}if(f) return ans1;return ans2;
}
int qus(int f,int x,int y)
{int ans1&＃61;0,ans2&＃61;-1e9;while(top[x]!&＃61;top[y]){if(dep[top[x]]<dep[top[y]]) swap(x,y);ans1&＃43;&＃61;ask(1,dfn[top[x]],dfn[x]);ans2&＃61;max(ans2,ask(0,dfn[top[x]],dfn[x]));x&＃61;fa[top[x]];}if(dep[x]>dep[y]) swap(x,y);ans1&＃43;&＃61;ask(1,dfn[x],dfn[y]);ans2&＃61;max(ans2,ask(0,dfn[x],dfn[y]));if(f) return ans1;return ans2;
}
void solve()
{int T;cin>>n;for(int i&＃61;1;i<n;i&＃43;&＃43;){int x,y;scanf("%lld%lld",&x,&y);addedge(x,y);}for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;) scanf("%lld",&a[i]);dfs1(1,1);dfs2(1,1);bulid();cin>>T;while(T--){string s;int x,y;cin>>s>>x>>y;if(s&＃61;&＃61;"CHANGE") change(dfn[x],y);else if(s&＃61;&＃61;"QMAX") printf("%lld\n",qus(0,x,y));else printf("%lld\n",qus(1,x,y));}
}
signed main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);cout.tie(0);solve();
// puts("");return 0;
}