怎么 acw 又没有这题的题解。

点分树

这题很像【点分树 | 震波】，也是统计树上点到某个点的问题，不过这题需要求带权重心。
设现在原树上有边 $(u,w)$，$w$ 子树的分治重心是 $v$，即点分树上有边 $(u,v)$。如何快速找到带权重心？
考虑先钦定点分树的根为带权重心，然后考虑往下找更优解。显然带权重心是唯一的，所以如果存在更优解一定只存在于一个子树。
因此在点分树上遍历所有 $(u,v)$，建树的时候可以顺便记一下这条边的 $w$（原树上该方向的连边指向谁），如果移动到 $w$ 更优那就把带权重心移动到 $v$，在 $v$ 的分治区域内继续求解。

考虑如何快速计算以一个点为“补给站”的答案？
在点分树上每个点记录如下三个信息：

1. suma：子树内权值和。
2. dis1：$u$ 子树内到 $u$ 的 $\sum\limits dist_v \times a_v$。
3. dis2：$u$ 子树内到 $fa_u$（点分树上父亲）的 $\sum\limits dist_v \times a_v$。

修改和模板是一样的，查询已经讲过了。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 15, M = N << 1;

int n, q;
struct Graph1 { //原树
    int h[N], e[M], w[M], ne[M], idx = 0;
    void add(int a, int b, int c) { e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++; }
    void addedge(int a, int b, int c) { add(a, b, c), add(b, a, c); }
    void build_graph() {
        for (int i = 1; i <= n; i++) h[i] = -1;
        for (int i = 1, a, b, c; i < n; i++) scanf("%lld%lld%lld", &a, &b, &c), addedge(a, b, c);
    }
    int dep[N], dis[N], dfn[N];
    int up[M][21], lg[M], tot = 0;

    void dfs(int u, int father) {
        up[++tot][0] = u, dfn[u] = tot;
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i];
            if (v == father) continue;
            dep[v] = dep[u] + 1, dis[v] = dis[u] + w[i];
            dfs(v, u);
            up[++tot][0] = u;
        }
    }

    int get(int u, int v) { return (dep[u] < dep[v]) ? u : v; }
    void init() {
        lg[1] = 0;
        for (int i = 2; i <= tot; i++) lg[i] = lg[i >> 1] + 1;
        for (int i = 1; i <= 19; i++)
            for (int j = 1; j <= tot; j++) {
                if (j + (1 << i) - 1 > tot) break;
                up[j][i] = get(up[j][i - 1], up[j + (1 << i - 1)][i - 1]);
            }
    }
    int mn(int l, int r) {
        if (l > r) swap(l, r);
        int len = lg[r - l + 1];
        return get(up[l][len], up[r - (1 << len) + 1][len]);
    }
    int lca(int u, int v) { return mn(dfn[u], dfn[v]); }
    int dist(int u, int v) { return dis[u] + dis[v] - 2 * dis[lca(u, v)]; }
} G1;

struct Graph2 { //点分树
    int h[N], e[N], s[N], ne[N], idx = 0;
    void add(int a, int b, int son) { e[idx] = b, s[idx] = son, ne[idx] = h[a], h[a] = idx++; }
    int suma[N], dis1[N], dis2[N], fa[N];
    bool st[N];

    int sz[N], Max[N], rt, root;  //原树的分治 sz
    void getsz(int u, int father, int all) {
        sz[u] = 1, Max[u] = 0;
        for (int i = G1.h[u]; ~i; i = G1.ne[i]) {
            int v = G1.e[i];
            if (v == father || st[v]) continue;
            getsz(v, u, all), sz[u] += sz[v], Max[u] = max(Max[u], sz[v]);
        }
        Max[u] = max(Max[u], all - sz[u]);
        if (!rt || Max[rt] > Max[u]) rt = u;
    }

    void dfs(int u) {
        st[u] = 1;
        for (int i = G1.h[u]; ~i; i = G1.ne[i]) {
            int v = G1.e[i];
            if (st[v]) continue;
            rt = 0, getsz(v, 0, sz[v]), getsz(rt, 0, sz[v]);
            fa[rt] = u, add(u, rt, v);  //原树上有 (u, v)，点分树上有 (u, rt)，即 v 是 rt 方向上的儿子
            dfs(rt);
        }
    }
    void build_graph() {
        for (int i = 1; i <= n; i++) h[i] = -1;
        rt = 0, getsz(1, 0, n), getsz(rt, 0, n);
        root = rt, dfs(root);
    }

    int getdis(int x) {    //求出以 x 作为补给站的答案
        int res = dis1[x];
        for (int u = x; fa[u]; u = fa[u]) {
            int out = dis1[fa[u]] - dis2[u];    // father 儿子中 u 的兄弟到 father 的贡献
            int down = (suma[fa[u]] - suma[u]) * G1.dist(x, fa[u]); //上面那些点从 father 再到 x
            res += out + down;
        }
        return res;
    }

    void update(int x, int delta) {
        suma[x] += delta;
        for (int u = x; fa[u]; u = fa[u]) {
            int dis = G1.dist(x, fa[u]);
            dis2[u] += delta * dis;
            dis1[fa[u]] += delta * dis;
            suma[fa[u]] += delta;
        }
    }
    int query(int u) {
        int ans = getdis(u);
        for (int i = h[u]; ~i; i = ne[i]) {
            int v = e[i], son = s[i];
            if (getdis(son) < ans) return query(v);
        }
        return ans;
    }
} G2;

void answer() { printf("%lld\n", G2.query(G2.root)); }

signed main() {
    scanf("%lld%lld", &n, &q);
    G1.build_graph();
    G1.dfs(1, 0), G1.init();
    G2.build_graph();


    while (q--) {
        int x, d; scanf("%lld%lld", &x, &d);
        G2.update(x, d);
        answer();
    }
    return 0;
}