题目传送门
题目大意
给定一棵树,初始点权都为0,要求支持:
- 修改点权
- 询问带权重心
询问带权重心就在点分树上跑一下就行了。(枚举跳哪个子树更优)
剩下都是基础点分治。
学了一下11-dimensional的2.2k动态点分治,然后写抄出来只有1.9k???
Code
/** * loj * Problem#2135 * Accepted * Time: 4492ms * Memory: 28404k */ #include <bits/stdc++.h> using namespace std; typedef bool boolean; typedef class Edge { public: int ed, w, ctr; Edge() { } Edge(int ed, int w) : ed(ed), w(w), ctr(-1) { } } Edge; #define ll long long const int N = 1e5 + 5; int n, m; boolean ban[N]; vector<Edge> G[N]; ll d[N][19], c[N], f[N]; int layer[N], faG[N], sz[N]; int get_sz(int p, int fa) { // calc size sz[p] = 1; for (auto& E : G[p]) sz[p] += ((E.ed == fa || ban[E.ed]) ? (0) : (get_sz(E.ed, p))); return sz[p]; } int get_G(int p, int fa, int hs) { for (auto& E : G[p]) { if ((E.ed ^ fa) && !ban[E.ed] && sz[E.ed] > hs) { return get_G(E.ed, p, hs); } } return p; } void prepare_dist(int p, int fa, int lay) { for (auto& E : G[p]) { if ((E.ed ^ fa) && !ban[E.ed]) { d[E.ed][lay] = d[p][lay] + E.w; prepare_dist(E.ed, p, lay); } } } int dividing(int x, int _faG, int lay) { int G = get_G(x, 0, get_sz(x, 0) >> 1); faG[G] = _faG, ban[G] = true; d[G][lay] = 0, layer[G] = lay; prepare_dist(G, 0, lay); for (auto& E : ::G[G]) { if (!ban[E.ed]) { E.ctr = dividing(E.ed, G, lay + 1); } } return G; } void update(int u, int v) { for (int p = u ; p; p = faG[p]) { f[p] += (d[u][layer[p]] - d[u][layer[p] - 1]) * v; c[p] += v; } } ll calc(int u) { ll ret = 0, lc = 0; for (int p = u; p; lc = c[p], p = faG[p]) { ret += f[p] + (c[p] - lc) * d[u][layer[p]]; } return ret; } ll solve(int u) { ll ans = calc(u); for (auto& E : G[u]) { if (~E.ctr && calc(E.ed) < ans) { return solve(E.ctr); } } return ans; } int main() { scanf("%d%d", &n, &m); for (int i = 1, u, v, w; i < n; i++) { scanf("%d%d%d", &u, &v, &w); G[u].emplace_back(v, w); G[v].emplace_back(u, w); } int ctr = dividing(1, 0, 1), u, e; while (m--) { scanf("%d%d", &u, &e); update(u, e); printf("%lld\n", solve(ctr)); } return 0; }