动态带权重心 学习笔记

· · 算法·理论

定义及基本性质

定义：在一棵点带权（权值非负，以下省略此前提）的树上，如果在树中选择某个节点并删除，这棵树将分为若干棵子树，统计子树点权和并记录最大值。取遍树上所有节点，使此最大值取到最小的节点被称为整个树的带权重心。点不带权的树的重心就是点权都为 1 的情况。

结论 1[^3]：点带正权的树的带权重心如果不唯一，则至多有两个，且这两个带权重心相邻。点带零权时，带权重心可能有很多。

结论 2[^3]：以树的带权重心为根时，所有子树的点权和都不超过整棵树点权和的一半。

引入边权

结论 3[^1]：使得从树上的任意一点出发到树上所有点的距离乘上目标点的点权和最小的起点一定是树的带权重心。 即带权重心是使 f(y)=\sum_x dis(x, y)a_x 取到最小值的 y。

证明：假设使得答案最小的起点是 u，对于一条连接 u 和 v 的长度为 c 的边，我们假设 u 那一侧的点权和为 s_u​，v 的那一侧点权和为 s_v​，那么如果有 s_u​<s_v​，那么我们将起点从 u 移动到 v，可以减少 (s_v​−s_u​)c 的带权距离，与 u 使得答案最小的假设矛盾。 从而 u 一定能保证它的每一个子树的权值和不超过总权值的一半，符合带权重心的定义。

注意，带权重心只和点权有关而和边权无关。

结论 4：枚举所有 y，\sum_x dis(x, y)a_x 的最小值是 \sum_{u}e(u,fa_u)\min(siz_u,siz_{rt}-siz_u)。

## 静态带权重心 根据定义或结论 2，可以在至多两次搜索内找到带权重心。 根据结论 3，可以做换根 DP，对每个 $y$ 求出 $\sum_x dis(x, y)a_x$ 的值，找到带权重心。 ## 动态带权重心 注意，我们讨论的动态带权重心是**单点修改点权，查询带权重心**这一问题。 ### 第一种做法：维护子树点权和 **推论 2.1**：以任意点为根时，子树的点权和**大于等于**整棵树点权和的一半的点中最深的那个点是带权重心。 **推论 2.2**：点带正权时，子树的点权和大于等于整棵树点权和的一半的点是根所在重链的前缀。 证明思路：这些点一定具有祖先关系，进而发现它们是重链前缀。 做法：用树剖线段树维护每个点的子树点权和，在线段树上二分即可。复杂度 $O(\log^2n)$。 ### 第二种做法：从下往上倍增 **结论 5[^1]**：**令任意一个节点为根，带权重心是带权 DFS 序的重心在树上所代表的节点的祖先。** 证明：我们假设所有节点权值和是 s，令任意一个节点为根，在带权 DFS 序中： - 重心出现的位置前面的节点权值和是其祖先节点权值和加上其祖先的所有排名在重心前面的节点的权值和，又注意到以重心为根节点时，这些节点同属于重心的原本的父亲的那一棵子树，由重心的性质知其权值和必定 $≤s/2​$。 - 重心的所有子树结束的位置，由上面的推理同理可知，其后面的权值和也 $≤s/2​$。 那么，带权 DFS 序重心在树的重心的子树内。 **推论 5.1[^1]**：令任意一个节点为根，带权重心子树权值和大于等于所有节点权值和的一半并且其任意一个子节点的子树权值和小于等于所有节点权值和的一半。 也就是说，带权 DFS 序重心到根的链上，存在一个分界点，分界点前的子树权值和大于等于 $s/2$，分界点前的子树权值和小于等于 $s/2$，分界点恰好是带权重心。 做法：分为两个部分，1. 确定带权 DFS 序重心 2. 倍增找带权重心。第一部分可以用树状数组二分做到 $O(\log n)$。第二部分可以倍增往上跳到第一个“子树权值和大于等于 $s/2$”的点，倍增算法可以且推荐换成斜二进制算法[^2]。由于子树权值和是动态的，因此这部分的复杂度是 $O(\log^2n)$。 第二部分可以用全局平衡二叉树优化至 $O(\log n)$[^1]。 ### 第三种做法：点分树 这是第一种做法的另一种实现。 **推论 3.1**：以带权重心为根，则对于不是根的点 $u$，有 $f(u)\geq f(fa_u)$。 做法：对原树建立点分树，查询时从点分树的根开始向下走，如果发现当前点的点分树儿子的 $f$ 比自己的小，那么递归子问题到这个儿子即可。这个做法用点分树同步计算出了带权重心的 $f$ 值，和点分树本身的结构很适配。复杂度可以做到 $O(\log^2n)$。可能需要将树进行三度化。 ## 计算 $f

结论 3 中引入的 f(y)=\sum_x dis(x, y)a_x 是我们需要考虑的另一个问题。这部分和前面的结论没有什么关系。

第一种做法：点分树

同上。复杂度可以做到 O(\log^2n)。

第二种做法：拆为链加链求和

记 d_i=dis(i,rt)。则

f(y)=\sum_x dis(x, y)a_x=\sum_x(d_x+d_y-2d_{lca(x,y)})a_x=\sum_x d_xa_x+d_y\sum_x a_x-2\sum_x d_{lca(x,y)}a_x

最后一个和式的维护方法：对于每个点，将其到根的链上所有边加上点权乘以边权，最后计算出 y 到根的链上的所有数的和。这部分就和 P4211[^4] 一样。那这里就只需要解决“链加、链求和”的问题，树剖线段树 O(\log^2n)，全局平衡二叉树 O(\log n)。

代码

以下是 P3345[^5] 的代码，使用“动态带权重心“的做法 2 和“计算 f” 的做法 2，时间复杂度 O((n+q)\log ^ 2n)，空间复杂度 O(n)。

#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
using LL = long long;
constexpr int N = 1e5 + 10;
struct fenwick {/*{{{*/
  LL t[N];
  void add(int x, LL k) {
    for (; x < N; x += x & -x) t[x] += k;
  }
  LL query(int x) {
    LL r = 0;
    for (; x > 0; x -= x & -x) r += t[x];
    return r;
  }
  int binary(LL k) {
    int p = 0;
    for (int j = __lg(N); j >= 0; j--) {
      int q = p | 1 << j;
      if (q < N && k > t[q]) k -= t[p = q];
    }
    return p + 1;
  }
} fen;/*}}}*/
int n, dfn[N], rnk[N], cnt, siz[N], q;
int fa[N], lb[N], dep[N];
vector<pair<int, int>> tr[N];
int upc[N];
namespace seg {/*{{{*/
  LL ans[N << 2], len[N << 2], tag[N << 2];
  void spread(int p, LL k) {
    tag[p] += k, ans[p] += k * len[p];
  }
  void maintain(int p) {
    ans[p] = ans[p << 1] + ans[p << 1 | 1];
  }
  void pushdown(int p) {
    spread(p << 1, tag[p]);
    spread(p << 1 | 1, tag[p]);
    tag[p] = 0;
  }
  void build(int p, int l, int r) {
    tag[p] = 0;
    if (l == r) return len[p] = upc[rnk[l]], ans[p] = 0, void();
    int mid = (l + r) >> 1;
    build(p << 1, l, mid);
    build(p << 1 | 1, mid + 1, r);
    maintain(p);
    len[p] = len[p << 1] + len[p << 1 | 1];
  }
  void modify(int ql, int qr, LL k, int p, int l, int r) {
    if (ql <= l && r <= qr) return spread(p, k);
    int mid = (l + r) >> 1;
    pushdown(p);
    if (ql <= mid) modify(ql, qr, k, p << 1, l, mid);
    if (mid < qr) modify(ql, qr, k, p << 1 | 1, mid + 1, r);
    maintain(p);
  }
  LL query(int ql, int qr, int p, int l, int r) {
    if (ql <= l && r <= qr) return ans[p];
    int mid = (l + r) >> 1;
    pushdown(p);
    LL res = 0;
    if (ql <= mid) res += query(ql, qr, p << 1, l, mid);
    if (mid < qr) res += query(ql, qr, p << 1 | 1, mid + 1, r);
    return res;
  }
};/*}}}*/
LL dis[N];
int son[N], top[N];
void dfs(int u, int p) {
  siz[u] = 1, son[u] = 0;
  int q = lb[p];
  dep[u] = dep[fa[u] = p] + 1;
  lb[u] = dep[p] - dep[q] != dep[q] - dep[lb[q]] ? p : lb[q];
  for (auto [v, w] : tr[u]) if (v != p) dis[v] = dis[u] + w, dfs(v, u), siz[u] += siz[v], upc[v] = w, siz[son[u]] < siz[v] && (son[u] = v);
}
void cut(int u, int topf) {
  dfn[u] = ++cnt, rnk[cnt] = u, top[u] = topf;
  if (son[u]) cut(son[u], topf);
  for (auto [v, w] : tr[u]) if (v != fa[u] && v != son[u]) cut(v, v);
}
void tc_add(int x, int y) {
  while (x) {
    seg::modify(dfn[top[x]], dfn[x], y, 1, 1, n);
    x = fa[top[x]];
  }
}
LL tc_query(int x) {
  LL res = 0;
  while (x) {
    res += seg::query(dfn[top[x]], dfn[x], 1, 1, n);
    x = fa[top[x]];
  }
  return res;
}
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);  
#endif
  cin >> n >> q;
  for (int i = 1, u, v, w; i < n; i++) {
    cin >> u >> v >> w;
    tr[u].emplace_back(v, w);
    tr[v].emplace_back(u, w);
  }
  cnt = 0, dfs(1, 0), cut(1, 1);
  LL ans1 = 0, ans2 = 0;
  seg::build(1, 1, n);
  while (q--) {
    int x, y;
    cin >> x >> y;
    ans1 += y;
    ans2 += dis[x] * y;
    fen.add(dfn[x], y);
    tc_add(x, y);
    auto sv = fen.query(n);
    int u = rnk[fen.binary((sv + 1) / 2)];
    debug("u0 = %d; ", u);
    auto piv = sv / 2;
    auto qsub = [&](int x) {
      return fen.query(dfn[x] + siz[x] - 1) - fen.query(dfn[x] - 1);
    };
    while (qsub(u) <= piv) u = lb[u] && qsub(lb[u]) <= piv ? lb[u] : fa[u];
    debug("u = %d; ", u);
    cout << ans1 * dis[u] + ans2 - 2 * tc_query(u) << endl;
  }
  return 0;
}

[^1]: 关于单点修改，查询树的带权重心的研究 - 洛谷专栏 [^2]: 斜二进制 LCA - 洛谷专栏 [^3]: 树的重心 - OI Wiki [^4]: P4211 LNOI2014 LCA - 洛谷 [^5]: P3345 ZJOI2015 幻想乡战略游戏 - 洛谷