D12 Luogu P3384【模板】轻重链剖分/树链剖分

标程20250114：

#include<bits/stdc++.h>
using namespace std; 
const int N=2e5+10;
vector<int> G[N];
int fa[N], son[N], dep[N], siz[N];
void dfs1(int x, int xfa) 
{
	fa[x] = xfa; dep[x] = dep[xfa] + 1; siz[x] = 1; son[x] = -1;
	for(int y : G[x]) if(y != xfa)
	{
		dfs1(y, x);
		siz[x] += siz[y];
		if(son[x] == -1 || siz[son[x]] < siz[y]) son[x] = y; //更新x的重儿子身份
	}
}
int tsp, dfn[N], _dfn[N], top[N];
void dfs2(int x, int tp) 
{ 
    dfn[x] = ++tsp; _dfn[tsp] = x; top[x] = tp; //_dfn[]只在线段树bt用到 
    if(son[x] > 0) dfs2(son[x], tp); 
    for(int y : G[x]) if(y != fa[x] && y != son[x])
    	dfs2(y, y);
}
#define lc(p) (p << 1)
#define rc(p) (p << 1 | 1)
struct trnode{ int l, r, c; }tr[N << 2];
int a[N];
void pushup(int p){ tr[p].c = max(tr[lc(p)].c, tr[rc(p)].c); }
void bt(int p, int l, int r) 
{ 
    tr[p] = {l, r, 0}; 
    if(l == r) { tr[p].c = a[_dfn[l]]; return ; }
    int m = (l + r) / 2;
    bt(lc(p), l, m); bt(rc(p), m + 1, r); 
    pushup(p);
} 
void change(int p, int x, int c) 
{ 
    if(x < tr[p].l || tr[p].r < x) return;
	if(tr[p].l == tr[p].r) { tr[p].c = c; return ; } 
    change(lc(p), x, c); change(rc(p), x, c); 
    pushup(p);
} 
int findmax(int p, int l, int r) 
{
	if(r < tr[p].l || tr[p].r < l) return 0;
    if(l <= tr[p].l && tr[p].r <= r) return tr[p].c;
    return max(findmax(lc(p), l, r), findmax(rc(p), l, r));
}  
int solve(int x, int y)//求点x至点y之间的最大值，点x到点y的边的新编号不是连续的，怎么办？ 
{ 
    int ret = 0; 
    for(; top[x] != top[y]; x = fa[top[x]]) 
    { 
        if(dep[top[x]] < dep[top[y]]) swap(x, y);
        ret = max(ret, findmax(1, dfn[top[x]], dfn[x])); 
    } 
    if(dep[x] > dep[y]) swap(x, y);  
    ret = max(ret, findmax(1, dfn[x], dfn[y])); 
    return ret;
} 
int main() 
{ 
    int n, m; scanf("%d%d", &n, &m); for(int i=1; i<=n; i++) scanf("%d", &a[i]); 
    for(int i=1, x, y; i < n; i++) 
    { 
        scanf("%d%d", &x, &y); 
        G[x].push_back(y);
		G[y].push_back(x);
    }
	dfs1(1, 0);
    tsp = 0; dfs2(1, 1);
    bt(1, 1, tsp);
    while(m--) 
    { 
        char s[10]; int x, y; scanf("%s%d%d", s, &x, &y); 
        if(s[0] == 'Q')   printf("%d\n", solve(x, y)); //求节点x和节点y之间的路径中权值最大的边。 
        else            change(1, dfn[x], y); //修改第新编号dfn[x]的点的值为y。 
    } 
    return 0; 
}