题解：动态带权重心与距离和

问题分析

我们有一棵带边权的树，点权会动态更新。每次操作后需要找到带权重心 $u$，并计算：

$$\sum_{v=1}^n \text{dist}(u,v) \cdot a_v$$

的最小值。

---

1. 带权重心的性质

关键性质：点 $u$ 是带权重心当且仅当对于 $u$ 的每个邻居 $v$，都有：

$$\sum_{w \in \text{component}(v)} a_w \le \frac{1}{2} \sum_{w=1}^n a_w $$

其中 $\text{component}(v)$ 是删除边 $(u,v)$ 后 $v$ 所在的连通分量。

换句话说，重心满足最大子树权重不超过总权重的一半。

---

2. 静态情况的解法

对于静态情况，我们可以：

1. 任选一个根（比如 $1$）
2. 计算每个点的子树权重和 $sz[u]$
3. 从根开始，如果存在一个子节点 $v$ 满足 $sz[v] > \frac{1}{2} \sum a_w$，则走向 $v$
4. 重复直到找不到这样的子节点，当前点就是重心

然后计算重心到所有点的带权距离和。

---

3. 动态情况的挑战

点权会动态变化，我们需要高效维护：

• 每个点的子树权重和
• 带权重心位置
• 重心到所有点的带权距离和

---

4. 算法框架：树链剖分 + 线段树

我们可以使用树链剖分来维护树结构，结合线段树支持：

维护的信息：

• $sz[u]$：以 $u$ 为根的子树的点权和
• $sum[u]$：以 $u$ 为根的子树的 $\sum_{v \in \text{subtree}(u)} \text{dist}(u,v) \cdot a_v$

操作：

1. 点权更新：从 $u$ 到根路径上的所有点更新 $sz$ 和 $sum$
2. 寻找重心：从当前重心开始，检查是否存在邻居满足条件，如果存在则移动
3. 计算答案：利用维护的信息快速计算

---

5. 关键观察

观察1：重心在点权变化时只会移动 $O(1)$ 步（类似树的重心的移动性质）。

观察2：带权距离和可以表示为：

$$\sum_v \text{dist}(u,v) \cdot a_v = \sum_v (\text{dist}(root,v) + \text{dist}(root,u) - 2 \cdot \text{dist}(root, \text{lca}(u,v))) \cdot a_v $$

但这样计算较复杂。

更好的方法：维护每个点到重心的距离，利用重心移动时路径重叠的性质。

---

6. 动态维护带权距离和

设 $F(u) = \sum_v \text{dist}(u,v) \cdot a_v$。

当重心从 $u$ 移动到邻居 $v$ 时：

$$F(v) = F(u) + (\text{dist}(u,v) \cdot (\text{total} - 2 \cdot sz[v])) $$

其中 $\text{total} = \sum a_w$，$sz[v]$ 是删除边 $(u,v)$ 后 $v$ 所在连通分量的点权和。

证明：

• 从 $u$ 到 $v$，$v$ 所在连通分量中的所有点距离减少 $\text{dist}(u,v)$
• 其他点的距离增加 $\text{dist}(u,v)$
• 所以变化量为：$-\text{dist}(u,v) \cdot sz[v] + \text{dist}(u,v) \cdot (\text{total} - sz[v])$
• 化简得：$\text{dist}(u,v) \cdot (\text{total} - 2 \cdot sz[v])$

---

7. 算法步骤

预处理：

1. 树链剖分，建立线段树
2. 计算每个点到根的距离 $dep[u]$
3. 初始重心为任意点（比如 $1$），初始 $F = 0$

每次操作 $u$ 点权加 $e$：

1. 更新从 $u$ 到根路径上所有点的 $sz$ 和 $sum$
2. 更新总权重 $\text{total} \gets \text{total} + e$
3. 从当前重心 $c$ 开始，检查每个邻居 $v$：
   • 计算 $sz_v$（$v$ 所在连通分量的权重）
   • 如果 $sz_v > \frac{1}{2} \text{total}$，则：
     • $F \gets F + \text{dist}(c,v) \cdot (\text{total} - 2 \cdot sz_v)$
     • $c \gets v$
     • 重复检查
4. 输出 $F$

---

8. 计算 $sz_v$

对于边 $(c,v)$，$v$ 所在连通分量的权重：

• 如果 $v$ 是 $c$ 的子节点：$sz_v = sz[v]$
• 如果 $v$ 是 $c$ 的父节点：$sz_v = \text{total} - sz[c]$

---

9. 复杂度分析

• 树链剖分：$O(n)$ 预处理
• 每次更新：$O(\log n)$ 更新路径
• 重心移动：$O(\deg(c) \log n)$，但均摊 $O(\log n)$
• 总复杂度：$O((n + q) \log n)$

---

10. 样例验证

样例输入：

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

逐步分析：

1. 初始：所有点权为0，重心任意，$F=0$ → 输出 0
2. 点3加1：重心可能在2或3，计算得 $F=1$ → 输出 1
3. 点8加1：重心移动，$F=4$ → 输出 4
4. 点3加1：$F=5$ → 输出 5
5. 点4加1：$F=6$ → 输出 6

与样例输出一致。

---

11. 实现细节

树链剖分部分：

// 预处理
void dfs1(int u, int fa) {
    sz[u] = 1; father[u] = fa; dep[u] = dep[fa] + 1;
    for (auto [v, w] : g[u]) {
        if (v == fa) continue;
        dist[v] = dist[u] + w;  // 到根的距离
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int topf) {
    top[u] = topf; dfn[u] = ++tim;
    if (son[u]) dfs2(son[u], topf);
    for (auto [v, w] : g[u]) {
        if (v == father[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}

线段树维护：

// 维护 sz 和 sum 的线段树
struct Node {
    long long sz, sum;
} tr[N << 2];

// 更新路径 u 到根
void update_path(int u, long long e) {
    while (u) {
        update(1, 1, n, dfn[top[u]], dfn[u], e);
        u = father[top[u]];
    }
}

重心移动：

int find_centroid(int c, long long total) {
    while (true) {
        bool moved = false;
        for (auto [v, w] : g[c]) {
            long long sz_v = (v == father[c]) ? total - query_sz(c) : query_sz(v);
            if (sz_v * 2 > total) {
                F += w * (total - 2 * sz_v);
                c = v;
                moved = true;
                break;
            }
        }
        if (!moved) break;
    }
    return c;
}

---

12. 完整代码框架

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

const int N = 100010;  // 根据数据范围调整

int n, q;
vector<pair<int, int>> g[N];  // 邻接表: (v, w)

// 树链剖分相关
int father[N], dep[N], sz[N], son[N], top[N], dfn[N], tim;
long long dist[N];  // 到根的距离

// 线段树维护 sz 和 sum
struct Node {
    long long sz, sum, lazy;
} tr[N << 2];

// 线段树操作
void pushup(int u) {
    tr[u].sz = tr[u<<1].sz + tr[u<<1|1].sz;
    tr[u].sum = tr[u<<1].sum + tr[u<<1|1].sum;
}

void pushdown(int u, int l, int r) {
    if (tr[u].lazy) {
        int mid = (l + r) >> 1;
        // 更新左右子树
        tr[u<<1].sz += tr[u].lazy * (mid - l + 1);
        tr[u<<1].sum += tr[u].lazy * (/*距离和计算*/);
        tr[u<<1].lazy += tr[u].lazy;
        
        tr[u<<1|1].sz += tr[u].lazy * (r - mid);
        tr[u<<1|1].sum += tr[u].lazy * (/*距离和计算*/);
        tr[u<<1|1].lazy += tr[u].lazy;
        
        tr[u].lazy = 0;
    }
}

void update(int u, int l, int r, int ql, int qr, long long e) {
    if (ql <= l && r <= qr) {
        tr[u].sz += e * (r - l + 1);
        tr[u].sum += e * (/*该段距离和*/);
        tr[u].lazy += e;
        return;
    }
    pushdown(u, l, r);
    int mid = (l + r) >> 1;
    if (ql <= mid) update(u<<1, l, mid, ql, qr, e);
    if (qr > mid) update(u<<1|1, mid+1, r, ql, qr, e);
    pushup(u);
}

long long query_sz(int u) {
    // 查询u的子树sz
    return query_sz_segment(1, 1, n, dfn[u], dfn[u] + sz[u] - 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n >> q;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
        g[v].emplace_back(u, w);
    }
    
    // 树链剖分预处理
    dfs1(1, 0);
    dfs2(1, 1);
    
    // 初始化线段树
    build(1, 1, n);
    
    int centroid = 1;
    long long total = 0, F = 0;
    
    while (q--) {
        int u; long long e;
        cin >> u >> e;
        
        // 更新点权
        update_path(u, e);
        total += e;
        
        // 寻找重心并更新F
        centroid = find_centroid(centroid, total);
        
        cout << F << '\n';
    }
    
    return 0;
}

---

总结

本题的关键在于：

1. 理解带权重心的性质
2. 利用重心移动时距离和的递推公式
3. 使用树链剖分高效维护子树信息
4. 动态维护重心位置和距离和

这是一个典型的树形数据结构问题，考察对树的性质和动态维护算法的掌握。