树链剖分

怎么说呢，感觉只要不是求最大最小值好像都可以用树上查分代替。

例题

[ZJOI2008] 树的统计 - 单点修改 树链查询

树链剖分板子，不多说了，代码注意细节就行。该用dfn的地方不要把点的编号传进去。

#include<bits/stdc++.h>
using namespace std;
#define ls (id<<1)
#define rs (id<<1 | 1)
const int N = 3e5 + 5;
int n, h[N], cnt, val[N], q, son[N], size[N], dep[N], fa[N], dfn[N], top[N], rnk[N], tot;
struct edge{ int v, nxt; }e[N];
struct node{ int l, r, mx, sum; }t[N<<2];
inline void add(int u, int v){ e[++cnt] = (edge){v, h[u]}; h[u] = cnt; }
inline void dfs1(int u){
	size[u] = 1, son[u] = -1;
	for(int i=h[u]; i; i=e[i].nxt){
		int v = e[i].v;
		if(!dep[v]){
			dep[v] = dep[u] + 1;
			fa[v] = u;
			dfs1(v);
			size[u] += size[v];
			if(son[u] == -1 || size[v] > size[son[u]]) son[u] = v;
		}
	}
}
inline void dfs2(int u, int t){
	top[u] = t, rnk[dfn[u]=++tot] = u;
	if(son[u] == -1) return;
	dfs2(son[u], t);
	for(int i=h[u]; i; i=e[i].nxt){
		int v = e[i].v;
		if(v != son[u] && v != fa[u]) dfs2(v, v);
	}
}
inline void pushup(int id){
	t[id].sum = t[ls].sum + t[rs].sum;
	t[id].mx = max(t[ls].mx, t[rs].mx);
}
inline void build(int id, int l, int r){
	t[id].l = l, t[id].r = r;
	if(l == r){
		t[id].mx = t[id].sum = val[rnk[l]];
		return;
	}
	int mid = (l + r) >> 1;
	build(ls, l, mid), build(rs, mid+1, r);
	pushup(id);
}
inline void modify(int id, int v){
	if(t[id].l == v && t[id].r == v){
		t[id].sum = t[id].mx = val[rnk[v]];
		return;
	}
	int mid = (t[id].l + t[id].r) >> 1;
	modify(v<=mid?ls:rs, v);
	pushup(id);
}
inline int query_sum(int id, int l, int r){
	if(t[id].l >= l && r >= t[id].r) return t[id].sum;
	int mid = (t[id].l + t[id].r) >> 1, ans = 0;
	if(l <= mid) ans += query_sum(ls, l, r);
	if(r > mid) ans += query_sum(rs, l, r);
	return ans;
}
inline int query_max(int id, int l, int r){
	if(t[id].l >= l && r >= t[id].r) return t[id].mx;
	int mid = (t[id].l + t[id].r) >> 1, ans = INT_MIN;
	if(l <= mid) ans = max(ans, query_max(ls, l, r));
	if(r > mid) ans = max(ans, query_max(rs, l, r));
	return ans;
}
inline int qsum(int u, int v){
	int tu = top[u], tv = top[v], ans = 0;
	while(tu != tv){
		if(dep[tu] > dep[tv])
			ans += query_sum(1, dfn[tu], dfn[u]), u = fa[tu];
		else 
			ans += query_sum(1, dfn[tv], dfn[v]), v = fa[tv];
		tu = top[u], tv = top[v];
	}
	if(dfn[u] >= dfn[v]) ans += query_sum(1, dfn[v], dfn[u]);
	else ans += query_sum(1, dfn[u], dfn[v]);
	return ans;
}
inline int qmax(int u, int v){
	int tu = top[u], tv = top[v], ans = INT_MIN;
	while(tu != tv){
		if(dep[tu] >= dep[tv])
			ans = max(ans, query_max(1, dfn[tu], dfn[u])), u = fa[tu];
		else
			ans = max(ans, query_max(1, dfn[tv], dfn[v])), v = fa[tv];
		tu = top[u], tv = top[v];
	}
	if(dfn[u] >= dfn[v]) ans = max(ans, query_max(1, dfn[v], dfn[u]));
	else ans = max(ans, query_max(1, dfn[u], dfn[v]));
	return ans;
}
signed main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin>>n;
	for(int i=1, a, b; i<n; ++i) cin>>a>>b, add(a, b), add(b, a);
	for(int i=1; i<=n; ++i) cin>>val[i];
	dep[1] = 1, fa[1] = 1, dfs1(1); dfs2(1, 1);
	build(1, 1, n);
	cin>>q;
	for(int i=1; i<=q; ++i){
		string opt; int a, b;
		cin>>opt>>a>>b;
		if(opt == "CHANGE") val[a] = b, modify(1, dfn[a]); //It's very easy to make mistakes
		else if(opt == "QMAX") cout<<qmax(a, b)<<'\n';
		else cout<<qsum(a, b)<<'\n';
	} return 0;
}