动态点分治模板题。听说代码复杂度也是复杂度的一部分?
题目大意
给定一棵 nnn 个点的树,边有边权,点有点权,支持修改点权与查询带权重心。操作总数为 qqq。
n,q≤100000n,q\le100000n,q≤100000
题目链接
题解
动态点分治维护一下距离,找重心的话从点分树上走一遍就好了。自己找其他人博客看吧
反正这篇文章的目的是展示代码。
代码
一直听人说动态点分治难写,但是我觉得这是最好写的结构……结果一看这题有不少写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;
}
zyz分治!