动态点分治模板题。听说代码复杂度也是复杂度的一部分？

题目大意

给定一棵 $n$ 个点的树，边有边权，点有点权，支持修改点权与查询带权重心。操作总数为 $q$。

$n,q\le 100000$

题目链接

BZOJ 3924

题解

动态点分治维护一下距离，找重心的话从点分树上走一遍就好了。自己找其他人博客看吧

反正这篇文章的目的是展示代码。

代码

一直听人说动态点分治难写，但是我觉得这是最好写的结构……结果一看这题有不少写3,4k的……然而我只写了2.2k……于是分享一下我写的很蒻的代码……

#include <bits/stdc++.h>
#define debug(x) std::cerr << #x << " = " << x << std::endl

typedef long long LL;

const int MAXN = 100031, MAXL = 19;

struct E {
    int v, w, ctr;

    E() {}
    E(int _v, int _w) : v(_v), w(_w) {}
};

std::vector<E> g[MAXN];

int sz[MAXN], f[MAXN], l[MAXN];
LL d[MAXN][MAXL], sd[MAXN], sf[MAXN], c[MAXN];
bool vis[MAXN];

int gs(int u, int p) {
    sz[u] = 1;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i].v;
        if (!vis[v] && v != p) sz[u] += gs(v, u);
    }
    return sz[u];
}

int ctrd(int u, int p, int hs) {
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i].v;
        if (!vis[v] && v != p && sz[v] > hs) return ctrd(v, u, hs);
    }
    return u;
}

void gdis(int u, int p, int ly) {
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i].v;
        if (!vis[v] && v != p) d[v][ly] = d[u][ly] + g[u][i].w, gdis(v, u, ly);
    }
}

int dcomp(int u, int ly) {
    int ctr = ctrd(u, 0, gs(u, 0) / 2);
    vis[ctr] = 1;
    gdis(ctr, 0, l[ctr] = ly);
    for (int i = 0; i < g[ctr].size(); i++) if (!vis[g[ctr][i].v]) f[g[ctr][i].ctr = dcomp(g[ctr][i].v, ly + 1)] = ctr;
    return ctr;
}

void update(int u, int e) {
    for (int p = u; p; p = f[p]) sd[p] += e * d[u][l[p]], sf[p] += e * d[u][l[p] - 1], c[p] += e;
}

LL calc(int u) {
    LL ans = 0;
    for (int p = u; p; p = f[p]) ans += sd[p] - sf[p] + c[p] * (d[u][l[p]] - d[u][l[p] - 1]);
    return ans;
}

int n = 0, q = 0, ctr = 0;

LL solve(int u) {
    LL ans = calc(u);
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i].v;
        if (l[v] > l[u] && calc(v) < ans) return solve(g[u][i].ctr);
    }
    return ans;
}

int main() {
    scanf("%d%d", &n, &q);
    for (int i = 1, u = 0, v = 0, w = 0; i < n; i++) scanf("%d%d%d", &u, &v, &w), g[u].push_back(E(v, w)), g[v].push_back(E(u, w));
    ctr = dcomp(1, 1);
    for (int u = 0, e = 0; q--; ) scanf("%d%d", &u, &e), update(u, e), printf("%lld\n", solve(ctr));
    return 0;
}