LCT(LINK-Cut Tree)题

题意分析
这是一道关于树上“崛起”的题目。我们先理解一下题意：
给定一棵$n$个节点的树，每个节点$i$有$a_i$次$“access”$操作。
每次崛起$（access）$城市$i$时，国家$i$会取得城市$i$到城市1路径上所有城市的控制权。
灾难度 = 崛起过程中与不同国家进行战争的次数（同一国家多次只计一次）。
求所有可能崛起顺序中，灾难度之和的最大值。
方法：将问题转化为 $LCT$ 模型：最大化$access$操作中轻重链切换的总次数。
核心结论：
对于每个节点$u$，设其子树中所有$a$的值之和为$S_u$，$u$的所有子树（包括$u$自己）中$a$的最大值为$M_u$。
那么节点$u$对答案的最大贡献为：

$min(S_u-1,2*(S_u - M_u))$

即：
当$2*M_u > S_u+1$时（某个子树或自己过大），贡献为：$2*(S_u-M_u)$。
否则，贡献为$S_u-1$。
修改操作的处理
当给$a_x$加上$w$时，只可能影响$x$到根的路径上的点的贡献。
关键观察：如果某个子树的$a$之和大于其父节点子树$a$之和的一半，那么这条边是"重边"，修改时贡献不变。
这启发我们用类似树链剖分的思想：

若某子树$sum \times 2 > $父节点总$sum$，则为重边

每个点到根路径上轻边数量是$O(\log \sum a)$级别的
用$LCT$维护这些重链，每次修改时只需要处理轻边变成重边的情况。
代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 400005;

int n, m;
ll a[N], ans;

// LCT 结构
struct Node {
    int ch[2], fa;
    ll sum, val, thin_sum;  // sum=子树总和, val=节点值, thin_sum=虚边子树和
} t[N];

vector<int> G[N];

bool isroot(int x) {
    return t[t[x].fa].ch[0] != x && t[t[x].fa].ch[1] != x;
}

void pushup(int x) {
    t[x].sum = t[x].val + t[t[x].ch[0]].sum + t[t[x].ch[1]].sum + t[x].thin_sum;
}

void rotate(int x) {
    int fa = t[x].fa, gfa = t[fa].fa;
    int k = (t[fa].ch[1] == x);
    if (isroot(fa)) t[gfa].ch[t[gfa].ch[1] == fa] = x;
    t[x].fa = gfa;
    if (t[x].ch[k ^ 1]) t[t[x].ch[k ^ 1]].fa = fa;
    t[fa].ch[k] = t[x].ch[k ^ 1];
    t[x].ch[k ^ 1] = fa;
    t[fa].fa = x;
    pushup(fa);
    pushup(x);
}

void splay(int x) {
    while (isroot(x)) {
        int fa = t[x].fa, gfa = t[fa].fa;
        if (isroot(fa))
            rotate((t[gfa].ch[1] == fa) ^ (t[fa].ch[1] == x) ? x : fa);
        rotate(x);
    }
}

// 计算节点 x 的贡献
// tot = x 子树的总和, maxx = x 的重儿子子树和（或自己的值）
ll calc(int x, ll tot, ll maxx) {
    if (t[x].ch[1]) return (tot - maxx) * 2;  // 有重儿子
    else if (t[x].val * 2 > tot) return (tot - t[x].val) * 2;  // 自己过大
    else return tot - 1;  // 都不是很大
}

// 修改操作：给节点 x 加上 w
void modify(int x, ll w) {
    splay(x);
    // tot = x 子树的总和（splay 中以 x 为根的子树）
    ll tot = t[x].sum - t[t[x].ch[0]].sum;
    ll maxx = t[t[x].ch[1]].sum;
    
    ans -= calc(x, tot, maxx);
    t[x].val += w;
    tot += w;
    t[x].sum += w;
    
    // 判断重边是否需要变化
    if (maxx * 2 < tot + 1) {
        // 原来的重儿子不再满足条件，变成虚边
        t[x].thin_sum += maxx;
        t[x].ch[1] = 0;
        maxx = 0;
    }
    ans += calc(x, tot, maxx);
    pushup(x);
    
    // 向上跳，处理祖先
    int son = x;
    for (x = t[son].fa; x; x = t[son = x].fa) {
        splay(x);
        tot = t[x].sum - t[t[x].ch[0]].sum;
        maxx = t[t[x].ch[1]].sum;
        
        ans -= calc(x, tot, maxx);
        t[x].thin_sum += w;
        tot += w;
        t[x].sum += w;
        
        // 原来的重儿子可能不再满足条件
        if (maxx * 2 < tot + 1) {
            t[x].thin_sum += maxx;
            t[x].ch[1] = 0;
            maxx = 0;
        }
        
        // 新的儿子可能变成重儿子
        if (t[son].sum * 2 > tot) {
            t[x].thin_sum -= t[son].sum;
            t[x].ch[1] = son;
            maxx = t[son].sum;
        }
        
        ans += calc(x, tot, maxx);
        pushup(x);
    }
}

// DFS 预处理
void dfs(int u, int fa) {
    t[u].sum = t[u].val = a[u];
    int pos = 0;
    ll maxx = a[u];
    
    for (int v : G[u]) {
        if (v == fa) continue;
        t[v].fa = u;
        dfs(v, u);
        t[u].sum += t[v].sum;
        if (t[v].sum > maxx) {
            maxx = t[v].sum;
            pos = v;
        }
    }
    
    // 计算 u 的贡献
    ans += min(t[u].sum - 1, (t[u].sum - maxx) * 2);
    
    // 设置重儿子
    if (maxx * 2 >= t[u].sum + 1) {
        t[u].ch[1] = pos;
    }
    
    // thin_sum = 所有虚边子树的和
    t[u].thin_sum = t[u].sum - t[u].val - t[t[u].ch[1]].sum;
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    
    dfs(1, 0);
    cout << ans << "\n";
    
    for (int i = 1; i <= m; i++) {
        int x;
        ll w;
        cin >> x >> w;
        modify(x, w);
        cout << ans << "\n";
    }
    
    return 0;
}

关键思路总结
1.
问题转化：将"崛起"操作转化为$LCT$的$access$操作，灾难度转化为轻重链切换次数
2.
独立贡献：每个节点的贡献可以独立计算，答案为各节点贡献之和
3.
贪心结论：对于每个节点，最大贡献为$\min(S-1, 2(S-M))$
4.
轻重链剖分：利用类似树剖的思想，重边修改时贡献不变，只需处理轻边
5.
$LCT$维护：用$LCT$维护重链结构，支持快速找到需要更新的轻边

点个赞呗