登录/ 注册
 找回密码
 立即注册
关闭

CSDN热搜

程序园 精品问答 技术交流 资源下载
返回列表 发新帖
首页 › 业界区 › 安全 ›2025北京集训Day1&Day3

2025北京集训Day1&Day3

庇床铍 昨天 21:01
树链剖分

重剖

对于一棵 \(n\) 个点的树，我们定义一个点的重儿子为它的所有儿子中子树大小最大的。
一个点与其重儿子的连边为重边，其他边为轻边。
定义重链为由若干条首尾相连的重边连成的极长链。
即（图源：OI-Wiki）：
1.png

重链有很好的性质：

  • 设以 \(u\) 为根的子树大小为 \(siz_u\)，则有其轻儿子的 \(siz_v\) 一定不超过 \(\frac {siz_u}2\)。证明：若 \(siz_v > \frac{siz_u}2\)，则一定不存在另一个儿子 \(v'\)，使得 \(siz_{v'}\ge siz_v\)，所以此时 \(v\) 一定不是轻儿子。
  • 任意两条重链都是不交的。证明：考虑两条重链相交一定存在一个点连接了超过两条重边，即除其父亲与该点的重边外，该点仍向儿子连了两条重边，而一个点最多有一个重儿子，矛盾。
  • 从树上的某个点到其祖先的过程中，最多经过不超过 \(\mathcal{O}(\log n)\) 条轻边。证明：过程中每经过一条边，就相当于当前点的 \(siz_u\) 变为 \(siz_{\mathrm{fa}_u}\)。如果经过的边为轻边，则根据第一个性质，有 \(siz_{\mathrm{fa}_u}\ge2siz_u\)，即每经过一条轻边，当前子树大小至少扩大 \(2\) 倍。最多有 \(n\) 个点，故最多扩大 \(\mathcal{O}(\log n)\) 次。
  • 若 dfs 时先走重儿子，再走轻儿子，则对于每条重链在该 dfs 序上一定是一段连续区间。证明：容易发现一定先走完一段连续的重边才走轻边，即先走完一条完整重链才走下一条。
根据这些性质，重链剖分就可以把树上两点间的路径问题转化成 \(\mathcal{O}(\log n)\) 段区间问题。
重剖模板：
  1. // dep[u] : u的深度
  2. // fa[u] ：u的直接父亲
  3. // siz[u] : 以 u 的子树大小
  4. // son[u] : u的重儿子
  5. // top[u] : u所在重链的深度最小的点
  6. void dfs(int u) {
  7.     dep[u] = dep[fa[u]] + 1, siz[u] = 1;
  8.     for (const int& v : e[u])
  9.         if (v != fa[u]) {
  10.             fa[v] = u, dfs(v), siz[u] += siz[v];
  11.             if (siz[v] > siz[son[u]]) son[u] = v;
  12.         }
  13. }
  15. void dfs(int u, int tp) {
  16.     top[u] = tp, dfn[num[u] = ++idx] = u;
  17.     if (son[u]) dfs(son[u], tp);
  18.     for (const int& v : e[u])
  19.         if (v != fa[u] && v != son[u])
  20.             dfs(v, v);
  21. }
复制代码
[LuoguP4211] [LNOI2014] LCA

pro.

给一棵 \(n\) 个点的有根树，\(m\) 次询问，每次询问给定 \(l,r,z\)，求 \(\sum_{i=l}^rdep_{\mathrm{lca}(i,z)}\)。
\(n,m\le5e4\)。\(1\mathrm{s},125\mathrm{MB}\)。
sol.

考虑暴力怎么做：每次询问枚举 \(i\)，暴力求 \(\mathrm{lca}(i,z)\) 统计答案。
显然优化要么快速求出一堆点与某个定点的 \(\mathrm{lca}\)，要么考虑把 \(\mathrm{lca}\) 转化。
前者显然不好做。
Trick：发现 \(dep_{\mathrm{lca}(i,z)}\) 等价于 \(i\) 和 \(z\) 的公共祖先个数。
我们给 \(i\) 到根的链上的点全部赋一个 \(1\) 的权值，则从 \(z\) 到根的链上的点权和即为答案。
考虑对于每个 \(z\)，我们让 \([l,~r]\) 的每个点到根链做一遍赋值，累加权值，最后统计 \(z\) 的根链和即为答案。
于是我们把不容易维护的 \(\mathrm{lca}\) 转化为了容易维护的根链加和根链查询和，树剖线段树很容易维护。
但这导致询问之间可能有相互影响，所以每次查询要清空线段树，复杂度难以接受。
把询问拆成 \([0,~r]-[0,~l-1]\)，然后离线询问，从 \([1,~n]\) 依次修改，每到一个点就在对应的询问上统计权值，复杂度 \(\mathcal{O}\big((n+m)\log^2 n\big)\)。
cod.
  1. #include <bits/stdc++.h>
  3. #define file(name, suf) ""#name"."#suf""
  4. #define input(name) freopen(file(name, in), "r", stdin)
  5. #define output(name) freopen(file(name, out), "w", stdout)
  7. constexpr int N = 5e4 + 10, Mod = 201314;
  8. int n, m, idx, fa[N], dep[N], siz[N], son[N], top[N], num[N];
  9. std::vector<int> e[N];
  10. struct Query { int r, z, ans, id; } q[N << 1];
  11. struct Seg_Tree {
  12.     struct Node { int len, sum, add; } t[N << 2];
  14.     #define ls (u << 1)
  15.     #define rs (u << 1 | 1)
  16.     #define mid ((l + r) >> 1)
  18.     void up(int u) { t[u].sum = (t[ls].sum + t[rs].sum) % Mod; }
  20.     void build(int u, int l, int r) {
  21.         t[u] = {r - l + 1, 0, 0};
  22.         if (l == r) return;
  23.         build(ls, l, mid), build(rs, mid + 1, r);
  24.     }
  26.     void add(int u, int x) {
  27.         t[u].sum = (t[u].sum + 1ll * x * t[u].len % Mod) % Mod;
  28.         t[u].add = (t[u].add + x) % Mod;
  29.     }
  31.     void down(int u) {
  32.         if (t[u].add) add(ls, t[u].add), add(rs, t[u].add), t[u].add = 0;
  33.     }
  35.     void add(int u, int l, int r, int ql, int qr, int x) {
  36.         if (l > qr || r < ql) return;
  37.         if (l >= ql && r <= qr) return add(u, x);
  38.         down(u);
  39.         add(ls, l, mid, ql, qr, x), add(rs, mid + 1, r, ql, qr, x), up(u);
  40.     }
  42.     int query(int u, int l, int r, int ql, int qr) {
  43.         if (l > qr || r < ql) return 0;
  44.         if (l >= ql && r <= qr) return t[u].sum;
  45.         down(u);
  46.         return (query(ls, l, mid, ql, qr) + query(rs, mid + 1, r, ql, qr)) % Mod;
  47.     }
  48. } T;
  50. void dfs(int u) {
  51.     dep[u] = dep[fa[u]] + 1, siz[u] = 1;
  52.     for (const int& v : e[u])
  53.         if (v != fa[u]) {
  54.             fa[v] = u, dfs(v), siz[u] += siz[v];
  55.             if (siz[v] > siz[son[u]]) son[u] = v;
  56.         }
  57. }
  59. void dfs(int u, int tp) {
  60.     top[u] = tp, num[u] = ++idx;
  61.     if (son[u]) dfs(son[u], tp);
  62.     for (const int& v : e[u])
  63.         if (v != fa[u] && v != son[u])
  64.             dfs(v, v);
  65. }
  67. void add(int u, int v, int x) {
  68.     while (top[u] != top[v]) {
  69.         if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
  70.         T.add(1, 1, n, num[top[u]], num[u], 1);
  71.         u = fa[top[u]];
  72.     }
  73.     if (dep[u] > dep[v]) std::swap(u, v);
  74.     T.add(1, 1, n, num[u], num[v], 1);
  75. }
  77. int query(int u, int v) {
  78.     int res = 0;
  79.     while (top[u] != top[v]) {
  80.         if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
  81.         res = (res + T.query(1, 1, n, num[top[u]], num[u])) % Mod;
  82.         u = fa[top[u]];
  83.     }
  84.     if (dep[u] > dep[v]) std::swap(u, v);
  85.     return (res + T.query(1, 1, n, num[u], num[v])) % Mod;
  86. }
  88. void solve() {
  89.     std::cin >> n >> m, T.build(1, 1, n);
  90.     for (int i = 2; i <= n; i++) {
  91.         int f;
  92.         std::cin >> f, ++f;
  93.         e[i].push_back(f), e[f].push_back(i);
  94.     }
  95.     for (int i = 1; i <= m; i++) {
  96.         int l, r, z;
  97.         std::cin >> l >> r >> z, ++l, ++r, ++z;
  98.         q[i].r = l - 1, q[i].z = z;
  99.         q[i + m].r = r, q[i + m].z = z;
  100.         q[i].id = q[i + m].id = i;
  101.     }
  102.     dfs(1), dfs(1, 1);
  103.     std::sort(q + 1, q + (m << 1) + 1, [](const Query& a, const Query& b) { return a.r < b.r; });
  104.     int now = 1;
  105.     while (now <= m << 1 && q[now].r < 1) now++;
  106.     for (int i = 1; i <= n; i++) {
  107.         add(1, i, 1);
  108.         while (now <= m << 1 && q[now].r == i)
  109.             q[now].ans = query(1, q[now].z), now++;
  110.     }
  111.     std::sort(q + 1, q + (m << 1) + 1, [](const Query& a, const Query& b) { return a.id == b.id ? a.r < b.r : a.id < b.id; });
  112.     for (int i = 1; i <= m << 1; i += 2) std::cout << ((q[i + 1].ans - q[i].ans) % Mod + Mod) % Mod << "\n";
  113. }
  115. int main() {
  116.     // input(Test), output(Test);
  117.     int _ = 1;
  118.     // std::cin >> _;
  119.     while (_--) solve();
  120.     return 0;
  121. }
复制代码
[LuoguP6798] 简单的树

pro.

给一棵 \(n\) 个点的有根树，点有点权 \(c_i\)。
定义点 \(u\) 的 \(val_u\) 为 \(\max_{v\in\mathrm{substree}_u}c_v\)。
定义函数 \(f(x,y)\) 为将 \(c_x\) 修改为 \(y\) 时整棵树的 \(\sum val_u\)。
\(q\) 次询问，每次询问给定 \(l,r,a\)，求 \(\sum_{i=l}^rf(a,i)\)。
强制在线。\(n,q\le5e5\)。\(\mathrm{3s,500MB}\)。
sol.

考虑 \(f(x,y)\) 怎么求。
容易发现修改 \(c_x\) 仅会影响到 \(x\) 及其祖先的 \(val\)，所以预处理出每条链上的 \(val\) 之和 \(dis\)，其他点的贡献即为整棵树的答案减去 \(dis_x\)。所以仅需要考虑修改后 \(x\) 根链的变化即可。
而每个点上将 \(c_x\) 改为 \(y\) 的答案等于删去 \(x\) 后的答案与 \(y\) 取较大值。于是对于 \(x\) 的某个祖先 \(u\)，若 \(val_u=c_x\)，则删去后的 \(val_u\) 应该等于子树中点权的次大值；否则不变，即子树中的最大值。于是我们可以 \(\mathcal{O}(n^2)\) 的回答一个询问。
观察 \(val_u\) 的定义，容易发现从一个点到根的路径上的点，\(val\) 单调不降。
于是必然存在某个 \(p\)，使得 \(x\) 到 \(p\) 的路径上的所有点均为次大值，\(\mathrm{fa}_p\) 到根的路径上的所有点均为最大值，故通过倍增即可 \(\mathcal{O}(\log n)\) 的找到 \(p\)，单次询问 \(\mathcal{O}(n\log n)\)。
发现我们要求的实际上是 \(\sum_{i=l}^r\sum\max(ans_u,i)\)，其中 \(u\) 为 \(x\) 的根链上的点， \(ans_u\) 为删去 \(x\) 后 \(u\) 的 \(val\)。
看到 \(\sum_{i=l}^r\) 的经典Trick就是差分为 \(\sum_{i=0}^r-\sum_{i=0}^{l-1}\)，于是我们只考虑 \(\sum_{i=0}^rf(a,i)\)。
考虑每个 \(u\)，若 \(ans_u\ge r\)，则贡献为 \(ans_u(r+1)\) ；否则，贡献为

\[\sum_{i=0}^r\max(ans_u,i)=\sum_{i=0}^{ans_u}ans_u+\sum_{i=ans_u+1}^ri=\frac{ans_u^2+ans_u+r^2+r}2\]
又由于之前的单调不降性质，对于 \(x\) 到 \(p\) 和 \(\mathrm{fa}_p\) 到根的路径上第一个满足 \(val_u\ge r\) 的点也是可以倍增的，即：
2.png

于是树剖后只需要用前缀和维护区间最大值、次大值的和、平方和即可。
实现时注意由于 \(lp,p,rp\) 的是否存在而导致的边界问题，细节较多。
cod.
  1. #include <bits/stdc++.h>
  3. #define file(name, suf) ""#name"."#suf""
  4. #define input(name) freopen(file(name, in), "r", stdin)
  5. #define output(name) freopen(file(name, out), "w", stdout)
  7. constexpr int N = 1e5 + 10;
  8. int n, m, idx, fa[N], dep[N], son[N], siz[N], top[N], dfn[N], num[N];
  9. std::vector<int> e[N];
  10. struct Node {
  11.     int l, r, len, ans, cvr;
  13.     Node operator + (const Node& b) {
  14.         Node res{};
  15.         res.ans = ans + b.ans + (r == b.l);
  16.         res.len = len + b.len;
  17.         res.l = l ? l : b.l, res.r = b.r ? b.r : r;
  18.         return res;
  19.     }
  20. };
  21. struct Seg_Tree {
  22.     Node t[N << 2];
  24.     #define ls (u << 1)
  25.     #define rs (u << 1 | 1)
  26.     #define mid ((l + r) >> 1)
  28.     void build(int u, int l, int r) {
  29.         t[u].len = r - l + 1, t[u].ans = 0;
  30.         if (l == r) return t[u].l = t[u].r = l, void();
  31.         build(ls, l, mid), build(rs, mid + 1, r), t[u] = t[ls] + t[rs];
  32.     }
  34.     void cover(int u, int x) {
  35.         t[u].l = t[u].r = t[u].cvr = x;
  36.         t[u].ans = t[u].len - 1;
  37.     }
  39.     void down(int u) {
  40.         if (t[u].cvr) cover(ls, t[u].cvr), cover(rs, t[u].cvr), t[u].cvr = 0;
  41.     }
  43.     void cover(int u, int l, int r, int ql, int qr, int x) {
  44.         if (l > qr || r < ql) return;
  45.         if (l >= ql && r <= qr) return cover(u, x);
  46.         down(u);
  47.         cover(ls, l, mid, ql, qr, x), cover(rs, mid + 1, r, ql, qr, x), t[u] = t[ls] + t[rs];
  48.     }
  50.     int query(int u, int l, int r, int k) {
  51.         if (l == r) return t[u].l;
  52.         down(u);
  53.         if (k <= mid) return query(ls, l, mid, k);
  54.         else return query(rs, mid + 1, r, k);
  55.     }
  57.     Node query(int u, int l, int r, int ql, int qr) {
  58.         if (l > qr || r < ql) return {0, 0, 0, 0, 0};
  59.         if (l >= ql && r <= qr) return t[u];
  60.         down(u);
  61.         return query(ls, l, mid, ql, qr) + query(rs, mid + 1, r, ql, qr);
  62.     }
  63. } T;
  65. void dfs(int u) {
  66.     dep[u] = dep[fa[u]] + 1, siz[u] = 1;
  67.     for (const int& v : e[u])
  68.         if (v != fa[u]) {
  69.             fa[v] = u, dfs(v), siz[u] += siz[v];
  70.             if (siz[v] > siz[son[u]]) son[u] = v;
  71.         }
  72. }
  74. void dfs(int u, int tp) {
  75.     dfn[num[u] = ++idx] = u, top[u] = tp;
  76.     if (son[u]) dfs(son[u], tp);
  77.     for (const int& v : e[u])
  78.         if (v != fa[u] && v != son[u])
  79.             dfs(v, v);
  80. }
  82. void cover(int u, int v, int x) {
  83.     while (top[u] != top[v]) {
  84.         if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
  85.         T.cover(1, 1, n, num[top[u]], num[u], x);
  86.         u = fa[top[u]];
  87.     }
  88.     if (dep[u] > dep[v]) std::swap(u, v);
  89.     T.cover(1, 1, n, num[u], num[v], x);
  90. }
  92. int query(int u, int v) {
  93.     Node L{}, R{}, res{};
  94.     while (top[u] != top[v]) {
  95.         if (dep[top[u]] > dep[top[v]]) {
  96.             res = T.query(1, 1, n, num[top[u]], num[u]);
  97.             std::swap(res.l, res.r);
  98.             L = L + res;
  99.             u = fa[top[u]];
  100.         } else {
  101.             res = T.query(1, 1, n, num[top[v]], num[v]);
  102.             R = res + R;
  103.             v = fa[top[v]];
  104.         }
  105.     }
  106.     if (dep[u] < dep[v]) {
  107.         res = T.query(1, 1, n, num[u], num[v]);
  108.         res = L + res + R;
  109.     } else {
  110.         res = T.query(1, 1, n, num[v], num[u]);
  111.         std::swap(res.l, res.r);
  112.         res = L + res + R;
  113.     }
  114.     return res.ans;
  115. }
  117. void solve() {
  118.     std::cin >> n >> m, T.build(1, 1, n), idx = 0;
  119.     for (int i = 1; i <= n; i++) e[i].clear(), son[i] = 0;
  120.     for (int i = 1; i < n; i++) {
  121.         int u, v;
  122.         std::cin >> u >> v;
  123.         e[u].push_back(v), e[v].push_back(u);
  124.     }
  125.     dfs(1), dfs(1, 1);
  126.     for (int i = 1; i <= m; i++) {
  127.         int op, u, v;
  128.         std::cin >> op >> u >> v;
  129.         if (op == 1) cover(u, v, i + n);
  130.         else std::cout << query(u, v) << "\n";
  131.     }
  132. }
  134. int main() {
  135.     // input(Test), output(Test);
  136.     std::cin.tie(nullptr)->sync_with_stdio(false);
  137.     int _ = 1;
  138.     std::cin >> _;
  139.     while (_--) solve();
  140.     return 0;
  141. }
复制代码
[QOJ9492] 树上简单求和

pro.

给定两棵 \(n\) 个点的有编号无根树（形态不保证相同），点的编号从 \(1\) 到 \(n\)，点 \(i\) 的点权为 \(a_i\)，两棵树共用点权。
有 \(m\) 次操作，每次操作给定 \(x,y,k\)，进行两步：
先对第一棵树上 \(x\) 到 \(y\) 的简单路径上的所有点的权值增加 \(k\) ；
再求出第二棵树上 \(x\) 到 \(y\) 的简单路径上的所有点的权值和，对 \(2^{64}\) 取模。
\(n,m\le 2e5\)。 \(\mathrm{6s,256MB}\)。
sol.

首先如果树是一条链，那么就变成了二维平面 \(x\) 区间加， \(y\) 区间和，可以规约矩阵乘法。所以本题显然不存在 \(\mathrm{poly} \log\) 的做法。
显然我不会规约矩乘
人话就是本题最优只能做到 \(\mathcal{O}(\sqrt n)\)。
树剖专题就不用其他科技了其实是我不会树分块，只做到 \(\mathcal{O}(m\sqrt n\log n)\)，可以通过。
首先通过树剖可以把树链操作转化为 \(\mathcal{O}(\log n)\) 个 dfs 序上的区间问题，所以以下只考虑区间问题。
假设我们已经实现了一个数据结构，支持在 \(\mathcal{O}(x)\) 的复杂度内对第二个序列单点修改，在 \(\mathcal{O}(y)\) 的复杂度内对第二个序列区间查询。
考虑如何修改：对第一个序列分块，散块直接暴力在第二个序列上单点修改，查询时通过第二个序列区间查询，共 \(\mathcal{O}(m\sqrt n)\) 次修改， \(\mathcal{O}(m)\) 次查询，故散块修改复杂度为 \(\mathcal{O}(mx\sqrt n)\)，查询复杂度为 \(\mathcal{O}(my)\)。为了根号平衡，我们发现，第二个序列上的数据结构应该支持 \(\mathcal{O}(1)\) 单点修改， \(\mathcal{O}(\sqrt n)\) 区间查询——还是分块。
整块修改依然考虑延迟标记，问题在于如何在查询时加入影响。
考虑前缀和，对于第一个序列的每个块，我们 \(\mathcal{O}(n)\) 预处理出第二个序列的每个前缀有多少个点落在该块内，区间查询时该块的对答案的影响为 \(tag_i\cdot (pre_{i,r}-pre_{i,l-1})\)。整块修改和查询都有 \(\mathcal{O}(m\sqrt n)\) 次，单次 \(\mathcal{O}(1)\)，故整块修改和查询复杂度均为 \(\mathcal{O}(m\sqrt n)\)。
于是算上树剖就可以在 \(\mathcal{O}(m\sqrt n\log n)\) 的时间内在线解决本题。
然后就被卡空间了（
但空间复杂度 \(\mathcal{O}(n\sqrt n)\approx9e7\)，大概在 \(\mathrm{350MB}\) 左右。
考虑优化空间，如果不维护序列的每个前缀，而仅维护整块的每个前缀，那么空间就变成了 \(\mathcal{O}(n)\) 的。
于是我们可以在 \(\mathcal{O}(\sqrt n)\) 的时间内解决整块对整块的影响，还需处理整块对散块的影响。
显然对于每个点有且仅有一个块将其包含，于是对每个散块的影响容易 \(\mathcal{O}(1)\) 查询。
于是做完了。时间 \(\mathcal{O}(m\sqrt n\log n)\)，空间 \(\mathcal{O}(n)\)。
实测块长 \(200\) 左右比较快。
cod.
  1. #include <bits/stdc++.h>
  3. #define file(name, suf) ""#name"."#suf""
  4. #define input(name) freopen(file(name, in), "r", stdin)
  5. #define output(name) freopen(file(name, out), "w", stdout)
  7. typedef long long ll;
  9. constexpr int N = 5e5 + 10, Mod = 998244353;
  10. int n, q, opt, c[N], inv_2;
  11. int idx, f[20][N], dep[N], siz[N], son[N], top[N], dfn[N], num[N];
  12. int m[N], nm[N], dis[N], s[4][N], ans;
  13. std::vector<int> e[N];
  15. ll qpow(ll a, ll b) {
  16.     ll res = 1;
  17.     while (b) {
  18.         if (b & 1) res = res * a % Mod;
  19.         a = a * a % Mod, b >>= 1;
  20.     }
  21.     return res;
  22. }
  24. void dfs(int u) {
  25.     m[u] = c[u], dep[u] = dep[f[0][u]] + 1, siz[u] = 1;
  26.     for (int i = 1; (1 << i) <= dep[u]; i++) f[i][u] = f[i - 1][f[i - 1][u]];
  27.     for (const int& v : e[u])
  28.         if (v != f[0][u]) {
  29.             f[0][v] = u, dfs(v), siz[u] += siz[v];
  30.             if (siz[v] > siz[son[u]]) son[u] = v;
  31.             if (m[v] > m[u]) nm[u] = m[u], m[u] = m[v];
  32.             else if (m[v] > nm[u]) nm[u] = m[v];
  33.             if (nm[v] > nm[u]) nm[u] = nm[v];
  34.         }
  35. }
  37. void dfs(int u, int tp) {
  38.     top[u] = tp, dfn[num[u] = ++idx] = u, dis[u] = (dis[f[0][u]] + m[u]) % Mod;
  39.     if (son[u]) dfs(son[u], tp);
  40.     for (const int& v : e[u])
  41.         if (v != f[0][u] && v != son[u])
  42.             dfs(v, v);
  43. }
  45. int query(int u, int v, int k) {
  46.     int res = 0;
  47.     while (top[u] != top[v]) {
  48.         if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
  49.         res = (res + s[k][num[u]] - s[k][num[top[u]] - 1]) % Mod;
  50.         u = f[0][top[u]];
  51.     }
  52.     if (dep[u] > dep[v]) std::swap(u, v);
  53.     return (res + s[k][num[v]] - s[k][num[u] - 1]) % Mod;
  54. }
  56. int query(int a, int r) {
  57.     int p = a, res = 1ll * (s[0][n] - dis[a]) * (r + 1) % Mod;
  58.     if (m[a] == c[a]) {
  59.         for (int i = std::__lg(dep[a]); ~i; i--) if (f[i][p] && m[f[i][p]] == c[a]) p = f[i][p];
  60.         if (nm[a] >= r) {
  61.             res = (res + 1ll * query(a, p, 2) * (r + 1) % Mod) % Mod;
  62.         } else {
  63.             int lp = a;
  64.             for (int i = std::__lg(dep[a] - dep[p] + 1); ~i; i--) {
  65.                 if (dep[f[i][lp]] >= dep[p] && nm[f[i][lp]] < r)
  66.                     lp = f[i][lp];
  67.             }
  68.             res = (res + (1ll * (query(a, lp, 3) + query(a, lp, 2)) % Mod + 1ll * r * (r + 1) % Mod * (dep[a] - dep[lp] + 1) % Mod) % Mod * inv_2 % Mod) % Mod;
  69.             if (lp != p) {
  70.                 res = (res + 1ll * query(f[0][lp], p, 2) * (r + 1) % Mod) % Mod;
  71.             }
  72.         }
  73.         if (p == 1) return (res + Mod) % Mod;
  74.         p = f[0][p];
  75.     }
  76.     if (m[p] >= r) {
  77.         res = (res + 1ll * query(p, 1, 0) * (r + 1) % Mod) % Mod;
  78.     } else {
  79.         int rp = p;
  80.         for (int i = std::__lg(dep[p] - 1); ~i; i--) {
  81.             if (f[i][rp] && m[f[i][rp]] < r)
  82.                 rp = f[i][rp];
  83.         }
  84.         res = (res + (1ll * (query(p, rp, 1) + query(p, rp, 0)) % Mod + 1ll * r * (r + 1) % Mod * (dep[p] - dep[rp] + 1) % Mod) % Mod * inv_2 % Mod) % Mod;
  85.         if (rp != 1) {
  86.             res = (res + 1ll * query(f[0][rp], 1, 0) * (r + 1) % Mod) % Mod;
  87.         }
  88.     }
  89.     return (res + Mod) % Mod;
  90. }
  92. void solve() {
  93.     std::cin >> n >> q >> opt, inv_2 = qpow(2, Mod - 2);
  94.     for (int i = 1; i <= n; i++) std::cin >> c[i];
  95.     for (int i = 1; i < n; i++) {
  96.         int u, v;
  97.         std::cin >> u >> v;
  98.         e[u].push_back(v), e[v].push_back(u);
  99.     }
  100.     dfs(1), dfs(1, 1);
  101.     for (int i = 1; i <= n; i++)
  102.         s[0][i] = (s[0][i - 1] + m[dfn[i]]) % Mod,
  103.         s[1][i] = (s[1][i - 1] + 1ll * m[dfn[i]] * m[dfn[i]] % Mod) % Mod,
  104.         s[2][i] = (s[2][i - 1] + nm[dfn[i]]) % Mod,
  105.         s[3][i] = (s[3][i - 1] + 1ll * nm[dfn[i]] * nm[dfn[i]] % Mod) % Mod;
  106.     while (q--) {
  107.         int l, r, a, x = 1ll * opt * ans % n;
  108.         std::cin >> l >> r >> a;
  109.         l = (l + x) % n + 1, r = (r + x) % n + 1, a = (a + x) % n + 1;
  110.         if (l > r) std::swap(l, r);
  111.         ans = ((query(a, r) - query(a, l - 1)) % Mod + Mod) % Mod;
  112.         std::cout << ans << "\n";
  113.     }
  114. }
  116. int main() {
  117.     // input(Test), output(Test);
  118.     std::cin.tie(nullptr)->sync_with_stdio(false);
  119.     int _ = 1;
  120.     // std::cin >> _;
  121.     while (_--) solve();
  122.     return 0;
  123. }
复制代码
[CF1017G] The Tree

pro.

\(n\) 个点的有根树，每个点有黑白两种颜色，初始全为白色。
定义三种操作，每种操作给定 \(x\) ：

  • 若 \(x\) 为白色，将其染黑并结束操作；否则对 \(x\) 的所有儿子执行该操作（若 \(x\) 为叶子也结束操作）；
  • 将 \(x\) 及其子树内的点全部染成白色；
  • 查询 \(x\) 的颜色。
共 \(q\) 次操作，对于操作三给出答案。
\(n,q\le1e5\)。 \(\mathrm{3s,256MB}\)。
sol.

先考虑没有操作二怎么做。
注意到一个点被染成黑色仅当其某个祖先进行了操作一，且操作的顺序不会影响答案，于是考虑把操作一转为单点加。
但这个条件仅是必要的，而一个点是否被染成黑色还受其根链的后缀有多少个点是白色有关，发现这个信息很难维护。
不妨设白色点的贡献为 \(-1\)，发现一个点被能被染成黑色当且仅当其根链上存在一段非负后缀和，于是操作一就转化为了单点修改和根链查询最大后缀和。
加上操作二：直接写成区间覆盖显然不对，因为现在判断一个点的颜色是通过根链，所以子树本身并不影响颜色。考虑查询的是区间后缀和，故初始化为 \(-1\) 的实质是使得白色点的最大后缀和为 \(-1\)，于是将整棵子树初始化为 \(-1\) 后，使得子树的根的最大后缀和为 \(-1\) 即可将其实现子树的初始化。
cod.
  1. #include <bits/stdc++.h>
  3. #define file(name, suf) ""#name"."#suf""
  4. #define input(name) freopen(file(name, in), "r", stdin)
  5. #define output(name) freopen(file(name, out), "w", stdout)
  6. #define map(type, x) static_cast<type>(x)
  8. typedef unsigned long long ull;
  10. constexpr int N = 2e5 + 1, B = 501;
  11. int n, m, b, cnt, pre[B][B], belong[N];
  12. ull a[N], tag[B], sum[B];
  13. struct Tree {
  14.     std::vector<int> e[N];
  15.     int idx, fa[N], dep[N], siz[N], son[N], top[N], num[N], dfn[N];
  17.     void dfs(int u) {
  18.         dep[u] = dep[fa[u]] + 1, siz[u] = 1;
  19.         for (const int& v : e[u])
  20.             if (v != fa[u]) {
  21.                 fa[v] = u, dfs(v), siz[u] += siz[v];
  22.                 if (siz[v] > siz[son[u]]) son[u] = v;
  23.             }
  24.     }
  26.     void dfs(int u, int tp) {
  27.         top[u] = tp, dfn[num[u] = ++idx] = u;
  28.         if (son[u]) dfs(son[u], tp);
  29.         for (const int& v : e[u])
  30.             if (v != fa[u] && v != son[u])
  31.                 dfs(v, v);
  32.     }
  34.     void init() {
  35.         for (int i = 1; i < n; i++) {
  36.             int u, v;
  37.             std::cin >> u >> v;
  38.             e[u].push_back(v), e[v].push_back(u);
  39.         }
  40.         dfs(1), dfs(1, 1);
  41.     }
  42. } T1, T2;
  44. void add(int l, int r, ull x) {
  45.     int L = belong[l], R = belong[r];
  46.     if (L == R) {
  47.         for (int i = l, j; i <= r; i++) {
  48.             j = T2.num[T1.dfn[i]];
  49.             a[T2.dfn[j]] += x, sum[belong[j]] += x;
  50.         }
  51.         return;
  52.     }
  53.     for (int i = l, j; belong[i] == L; i++) {
  54.         j = T2.num[T1.dfn[i]];
  55.         a[T2.dfn[j]] += x, sum[belong[j]] += x;
  56.     }
  57.     for (int i = L + 1; i < R; i++) tag[i] += x;
  58.     for (int i = r, j; belong[i] == R; i--) {
  59.         j = T2.num[T1.dfn[i]];
  60.         a[T2.dfn[j]] += x, sum[belong[j]] += x;
  61.     }
  62. }
  64. void Add(int u, int v, ull k) {
  65.     int x = u, y = v;
  66.     int *dep = T1.dep, *top = T1.top, *fa = T1.fa, *num = T1.num;
  67.     while (top[u] != top[v]) {
  68.         if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
  69.         add(num[top[u]], num[u], k), u = fa[top[u]];
  70.     }
  71.     if (dep[u] > dep[v]) std::swap(u, v);
  72.     add(num[u], num[v], k);
  73.     int l = dep[u] < dep[v] ? u : v;
  74. }
  76. ull query(int l, int r) {
  77.     ull res = 0;
  78.     int L = belong[l], R = belong[r];
  79.     if (L == R) {
  80.         for (int i = l; i <= r; i++) res += a[T2.dfn[i]] + tag[belong[T1.num[T2.dfn[i]]]];
  81.         return res;
  82.     }
  83.     for (int i = l; belong[i] == L; i++) res += a[T2.dfn[i]] + tag[belong[T1.num[T2.dfn[i]]]];
  84.     for (int i = L + 1; i < R; i++) res += sum[i];
  85.     if (R > L + 1) for (int i = 1; i <= cnt; i++) res += tag[i] * (pre[i][R - 1] - pre[i][L]);
  86.     for (int i = r; belong[i] == R; i--) res += a[T2.dfn[i]] + tag[belong[T1.num[T2.dfn[i]]]];
  87.     return res;
  88. }
  90. ull Query(int u, int v) {
  91.     ull res = 0;
  92.     int *dep = T2.dep, *top = T2.top, *fa = T2.fa, *num = T2.num;
  93.     while (top[u] != top[v]) {
  94.         if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
  95.         res += query(num[top[u]], num[u]), u = fa[top[u]];
  96.     }
  97.     if (dep[u] > dep[v]) std::swap(u, v);
  98.     return res + query(num[u], num[v]);
  99. }
  101. void solve() {
  102.     std::cin >> n >> m, b = map(int, sqrt(n));
  103.     for (int i = 1; i <= n; i++) std::cin >> a[i], belong[i] = (i - 1) / b + 1;
  104.     T1.init(), T2.init(), cnt = belong[n];
  105.     for (int i = 1; i <= n; i++) sum[belong[i]] += a[T2.dfn[i]], pre[belong[T1.num[i]]][belong[T2.num[i]]]++;
  106.     for (int i = 1; i <= cnt; i++) for (int j = 1; j <= cnt; j++) pre[i][j] += pre[i][j - 1];
  107.     while (m--) {
  108.         int x, y;
  109.         ull k;
  110.         std::cin >> x >> y >> k;
  111.         Add(x, y, k), std::cout << Query(x, y) << "\n";
  112.     }
  113. }
  115. int main() {
  116.     // input(Test), output(Test);
  117.     std::cin.tie(nullptr)->sync_with_stdio(false);
  118.     int _ = 1;
  119.     // std::cin >> _;
  120.     while (_--) solve();
  121.     return 0;
  122. }
复制代码
树上启发式合并 (dsu on tree)

依旧像重剖一样定义重儿子，每个点在统计答案时先继承重儿子答案，再遍历所有轻儿子及其子树中的点统计答案，这样做复杂度是 \(\mathcal{O}(n\log n)\) 的。
证明：考虑每个点被遍历到当且仅当它的某个祖先被作为轻儿子统计，故每个点被遍历的次数即为其根链上的轻边个数。而重剖的性质告诉我们：每个点的根链上最多只有 \(\mathcal{O}(\log n)\) 条轻边，故总复杂度 \(\mathcal{O}(n\log n)\)。证毕。
实现时对于每个点，先统计轻儿子答案，然后清空对父亲答案的影响，再统计重儿子答案并保留影响，最后再统计一遍轻儿子影响即可。
所以树上启发式合并常被用于解决某些可离线的树上问题。
[CF1709E] XOR Tree

pro.

\(n\) 个点的树，点有点权。
定义一棵树是好的，当且仅当其不存在一条简单路径上点权的异或和为 \(0\)。
你可以修改任意点的点权为任意正整数，求使这棵树变好的最小操作次数。
\(n\le2e5\)。 \(\mathrm{3s,250MB}\)。
sol.

首先注意到一旦我们对某个点进行修改，我们就可以使所有经过这个点的最短路径的异或和不为 \(0\) （一种方案将其修改为某个极大的 \(2^k\) 的形式）。于是一旦某个点被进行了修改，就可以删去它及它的子树。
一个常用的Trick：树上路径的点权广义和 \(dist(u,v)=dis_u+dis_v-2dis_{\mathrm{lca}(u,v)}+a_{\mathrm{lca}(u,v)}\)，其中 \(dis_u\) 表示 \(u\) 到根的点权广义和。
由于 \(\bigoplus\) 具有自反性，所以 \(dist(u,v)=dis_u\bigoplus dis_v\bigoplus a_{\mathrm{lca}(u,v)}\)。
于是我们用 std::set 维护子树内的 \(dis_u\) 集合，对于 \(u\) 的一棵子树，先遍历子树集合，统计当前 \(u\) 的集合中是否存在 \(dis_v\bigoplus a_u\)，若存在就把 \(a_u\) 修改并最后清空 \(u\) 集合，否则就把子树集合合并到 \(u\) 集合上。
使用启发式合并即可做到 \(\mathcal{O}(n\log^2 n)\)。
cod.
  1. #include <bits/stdc++.h>
  3. #define file(name, suf) ""#name"."#suf""
  4. #define input(name) freopen(file(name, in), "r", stdin)
  5. #define output(name) freopen(file(name, out), "w", stdout)
  7. constexpr int N = 1e5 + 10;
  8. int n, q, idx, fa[N], siz[N], son[N], top[N], num[N];
  9. std::vector<int> e[N];
  10. std::string ans[2] = {"white\n", "black\n"};
  11. struct Node {
  12.     int sum, suf, len;
  13.     bool cvr, empty;
  15.     Node operator + (const Node& b) {
  16.         if (empty & b.empty) return {0, 0, 0, false, true};
  17.         if (empty) return b;
  18.         else if (b.empty) return *this;
  19.         Node res{};
  20.         res.sum = sum + b.sum, res.suf = std::max(b.suf, suf + b.sum), res.len = len + b.len;
  21.         return res;
  22.     }
  23. };
  24. struct Seg_Tree {
  25.     Node t[N << 2];
  27.     #define ls (u << 1)
  28.     #define rs (u << 1 | 1)
  29.     #define mid ((l + r) >> 1)
  31.     void build(int u, int l, int r) {
  32.         t[u] = {-(r - l + 1), -1, r - l + 1, false, false};
  33.         if (l == r) return;
  34.         build(ls, l, mid), build(rs, mid + 1, r);
  35.     }
  37.     void add(int u, int x) {
  38.         t[u].sum += x, t[u].suf += x;
  39.     }
  41.     void cover(int u) {
  42.         t[u].sum = -t[u].len, t[u].suf = -1, t[u].cvr = true;
  43.     }
  45.     void down(int u) {
  46.         if (t[u].cvr) cover(ls), cover(rs), t[u].cvr = false;
  47.     }
  49.     void add(int u, int l, int r, int k, int x) {
  50.         if (l == r) return add(u, x), void();
  51.         down(u);
  52.         if (k <= mid) add(ls, l, mid, k, x);
  53.         else add(rs, mid + 1, r, k, x);
  54.         t[u] = t[ls] + t[rs];
  55.     }
  57.     void cover(int u, int l, int r, int ql, int qr) {
  58.         if (l > qr || r < ql) return;
  59.         if (l >= ql && r <= qr) return cover(u);
  60.         down(u), cover(ls, l, mid, ql, qr), cover(rs, mid + 1, r, ql, qr), t[u] = t[ls] + t[rs];
  61.     }
  63.     Node query(int u, int l, int r, int ql, int qr) {
  64.         if (l > qr || r < ql) return {0, 0, 0, false, true};
  65.         if (l >= ql && r <= qr) return t[u];
  66.         down(u);
  67.         return query(ls, l, mid, ql, qr) + query(rs, mid + 1, r, ql, qr);
  68.     }
  69. } T;
  71. void dfs(int u) {
  72.     siz[u] = 1;
  73.     for (const int& v : e[u])
  74.         if (v != fa[u]) {
  75.             fa[v] = u, dfs(v), siz[u] += siz[v];
  76.             if (siz[v] > siz[son[u]]) son[u] = v;
  77.         }
  78. }
  80. void dfs(int u, int tp) {
  81.     top[u] = tp, num[u] = ++idx;
  82.     if (son[u]) dfs(son[u], tp);
  83.     for (const int& v : e[u]) if (v != fa[u] && v != son[u]) dfs(v, v);
  84. }
  86. void add(int u, int x) { T.add(1, 1, n, num[u], x); }
  88. Node query(int u) {
  89.     Node res = {0, 0, 0, false, true};
  90.     while (fa[top[u]]) res = T.query(1, 1, n, num[top[u]], num[u]) + res, u = fa[top[u]];
  91.     res = T.query(1, 1, n, 1, num[u]) + res;
  92.     return res;
  93. }
  95. void cover(int u) {
  96.     T.cover(1, 1, n, num[u], num[u] + siz[u] - 1);
  97.     Node res = query(u);
  98.     if (res.suf < 0) return;
  99.     T.add(1, 1, n, num[u], -res.suf - 1);
  100. }
  102. void solve() {
  103.     std::cin >> n >> q;
  104.     for (int i = 2; i <= n; i++) {
  105.         int x;
  106.         std::cin >> x;
  107.         e[i].push_back(x), e[x].push_back(i);
  108.     }
  109.     dfs(1), dfs(1, 1), T.build(1, 1, n);
  110.     // for (int i = 1; i <= n; i++) std::cout << T.query(1, 1, n, num[i], num[i]).sum << " ";
  111.     // std::cout << "\n";
  112.     while (q--) {
  113.         int op, x;
  114.         std::cin >> op >> x;
  115.         if (op == 1) add(x, 1);
  116.         else if (op == 2) cover(x);
  117.         else {
  118.             std::cout << ans[query(x).suf >= 0];
  119.             // Node res = query(x);
  120.             // std::cout << res.sum << " " << res.suf << "\n";
  121.         }
  122.         // for (int i = 1; i <= n; i++) std::cout << i << " " << T.query(1, 1, n, num[i], num[i]).sum << " " << T.query(1, 1, n, num[i], num[i]).suf << "\n";
  123.         // std::cout << "\n";
  124.     }
  125. }
  127. int main() {
  128.     // input(Test), output(Test);
  129.     int _ = 1;
  130.     // std::cin >> _;
  131.     while (_--) solve();
  132.     return 0;
  133. }
复制代码
[CF600E] Lomsat gelral

pro.

\(n\) 个点的有根树，每个点有一种颜色，对于每个点求出其子树中出现次数最多的颜色的编号之和。
\(n\le1e5\)。 \(\mathrm{2s,256MB}\)。
sol.

全局开一个桶，维护子树中每个颜色出现了多少次，同时统计答案，加点是容易的，于是树上启发式合并即可。
复杂度 \(\mathcal{O}(n\log n)\)。
cod.
  1. // dep[u] : u的深度
  2. // fa[u] ：u的直接父亲
  3. // siz[u] : 以 u 的子树大小
  4. // son[u] : u的重儿子
  5. // well[u] : u子树内的最大深度
  6. // top[u] : u所在长链的深度最小点
  7. // len[u] : u所在长链的深度最大点到u的距离（len[top[u]]即为长链长度）
  8. void dfs(int u) {
  9.     for (int i = 1; i <= 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  10.     well[u] = dep[u] = dep[fa[u][0]] + 1;
  11.     for (const int& v : e[u])
  12.         if (v != fa[u][0]) {
  13.             dfs(v), well[u] = std::max(well[u], well[v]);
  14.             if (well[v] > well[son[u]]) son[u] = v;
  15.         }
  16. }
  18. void dfs(int u, int tp) {
  19.     top[u] = tp, len[u] = well[u] - dep[tp] + 1;
  20.     if (son[u]) dfs(son[u], tp);
  21.     for (const int& v : e[u])
  22.         if (v != fa[u][0] && v != son[u])
  23.             dfs(v, v);
  24. }
复制代码
[Atcoder-Code Festival 2017-Final-J] Tree MST

pro.

有一张 \(n\) 个点的完全图。给定一棵 \(n\) 个点的树，点有点权，边有边权。
完全图上 \(u,v\) 两点之间的边权为 \(w_u+w_v+\mathrm{dis}(u,v)\)，其中 \(w_u\) 为 \(u\) 的点权，\(\mathrm{dis}(u,v)\) 为树上两点简单路径上的边权和。
求完全图的最小生成树边权和。
\(n\le2e5\)。\(\mathrm{5s,256MB}\)。
sol.

定理：对于（一般）完全图最小生成树问题，可以先任选一个边集跑一遍最小生成树，把选中的边保留下来，再与其余边跑一遍最小生成树即为答案。
推论（Trick）：对于原图的边集 \(E\)，若有 \(\bigcup_{i=1}^kE_i=E\)，则先对 \(E_i\) 分别求得最小生成树，对被选中的边构成的集合求出的最小生成树等于直接对 \(E\) 求得的最小生成树。
观察到两点间的距离仍然和路径有关，考虑点分治。
根据推论，对于每一个分治中心，只需要先求出其在点分树上的子树内点的最小生成树，最后对所有保留的边做一遍 Kruskal 即可。由于每个点只会在其点分树的祖先上连一条边，故总边数 \(\mathcal{O}(n\log n)\)，最后 Kruskal 复杂度 \(\mathcal{O}(n\log^2n)\)。
于是问题变为如何快速对一个分治中心求出最小生成树。记 \(dis_u\) 为 \(u\) 到当前分治中心的距离，则完全图上 \((u,v)\) 的边权即为 \(w_u+w_v+dis_u+dis_v\)。贪心的想，每个点向 \(w_u+dis_u\) 最小的点连边即为最小生成树。对于 \(u,v\) 在同一棵子树内的情况，由于一定比全局答案劣，所以也不需要排除。点分治连边部分复杂度 \(\mathcal{O}(n\log n)\)。
总复杂度 \(\mathcal{O}(n\log^2n)\)。
cod.
  1. #include <bits/stdc++.h>
  3. typedef long long ll;
  4. typedef unsigned int ui;
  5. ui s;
  7. inline ui get(ui x) {
  8.     x ^= x << 13;
  9.     x ^= x >> 17;
  10.     x ^= x << 5;
  11.     return s = x;
  12. }
  14. const int N = 5e5 + 10;
  15. int n, q, root, fa[N][21], dep[N], well[N], son[N], top[N], len[N], ans;
  16. std::vector<int> e[N], up[N], down[N];
  17. ll output;
  19. void dfs(int u) {
  20.     for (int i = 1; i <= 20; i++) fa[u][i] = fa[fa[u][i - 1]][i - 1];
  21.     well[u] = dep[u] = dep[fa[u][0]] + 1;
  22.     for (const int& v : e[u])
  23.         if (v != fa[u][0]) {
  24.             dfs(v), well[u] = std::max(well[u], well[v]);
  25.             if (well[v] > well[son[u]]) son[u] = v;
  26.         }
  27. }
  29. void dfs(int u, int tp) {
  30.     top[u] = tp, len[u] = well[u] - dep[tp] + 1;
  31.     if (u == tp) for (int i = 1, anc = fa[u][0], des = son[u]; i <= len[u]; i++, anc = fa[anc][0], des = son[des]) up[u].push_back(anc), down[u].push_back(des);
  32.     if (son[u]) dfs(son[u], tp);
  33.     for (const int& v : e[u])
  34.         if (v != fa[u][0] && v != son[u])
  35.             dfs(v, v);
  36. }
  38. void ask(int& x, int& k) {
  39.     x = (get(s) ^ ans) % n + 1;
  40.     k = (get(s) ^ ans) % dep[x];
  41. }
  43. int find(int x, int k) {
  44.     if (!k) return x;
  45.     int t = static_cast<int>(log2(k));
  46.     x = fa[x][t], k -= (1 << t) + dep[x] - dep[top[x]], x = top[x];
  47.     return k == 0 ? x : (k > 0 ? up[x][k - 1] : down[x][-k - 1]);
  48. }
  50. void solve() {
  51.     std::cin >> n >> q >> s;
  52.     for (int i = 1; i <= n; i++) std::cin >> fa[i][0], root = fa[i][0] == 0 ? i : root, e[i].push_back(fa[i][0]), e[fa[i][0]].push_back(i);
  53.     dfs(root), dfs(root, root);
  54.     for (int i = 1, x, k; i <= q; i++) ask(x, k), ans = find(x, k), output ^= (ll)i * ans;
  55.     std::cout << output << "\n";
  56. }
  58. int main() {
  59.     int _ = 1;
  60.     while (_--) solve();
  61.     return 0;
  62. }
复制代码
[QOJ7855] 不跳棋

pro.

\(n\) 个点的树，每个点初始均有一个棋子。
共操作 \(n-2\) 次，每次拿走一个棋子。
求出每次操作后任意两个不同棋子之间的最短距离及点对数。
强制在线。
\(n\le5e5\)。\(\mathrm{5s,512MB}\)。
sol.

对于每一个状态显然可以用点分治 \(\mathcal{O}(n\log n)\) 完成，问题在于如何修改。
考虑建出点分树，显然删去某个点只会影响其 \(\mathcal{O}(\log n)\) 个祖先的路径信息。
于是对每个分治中心维护一个桶 \(cnt_x\) 表示到该分治中心的距离为 \(x\) 的点的数量，并维护最小值和次小值指针 \(min,cmin\)，再对全局开一个桶 \(ans_x\) 表示距离为 \(x\) 的点对数，并维护全局最小值指针。
容易发现删点答案单调不降，暴力维护指针均摊 \(\mathcal{O}(1)\) 。
总的时空复杂度均为 \(\mathcal{O}(n\log n)\) 。
cod.
  1. #include <bits/stdc++.h>
  3. #define file(name, suf) ""#name"."#suf""
  4. #define input(name) freopen(file(name, in), "r", stdin)
  5. #define output(name) freopen(file(name, out), "w", stdout)
  7. constexpr int N = 1e6 + 10;
  8. int n, len[N], son[N], b[N], *g[N], ans[N];
  9. int *now = b;
  10. std::vector<int> e[N];
  12. void dfs(int u, int f) {
  13.     for (const int& v : e[u])
  14.         if (v != f) {
  15.             dfs(v, u);
  16.             if (len[v] > len[son[u]]) son[u] = v;
  17.         }
  18.     len[u] = len[son[u]] + 1;
  19. }
  21. void dp(int u, int f) {
  22.     g[u][0] = 1;
  23.     if (son[u]) g[son[u]] = g[u] + 1, dp(son[u], u), ans[u] = ans[son[u]] + 1;
  24.     for (const int& v : e[u])
  25.         if (v != f && v != son[u]) {
  26.             g[v] = now, now += len[v], dp(v, u);
  27.             for (int i = 1; i <= len[v]; i++) {
  28.                 g[u][i] += g[v][i - 1];
  29.                 if (g[u][i] > g[u][ans[u]]) ans[u] = i;
  30.                 else if (g[u][i] == g[u][ans[u]] && i < ans[u]) ans[u] = i;
  31.             }
  32.         }
  33.     if (g[u][ans[u]] == 1) ans[u] = 0;
  34. }
  36. void solve() {
  37.     std::cin >> n;
  38.     for (int i = 1; i < n; i++) {
  39.         int u, v;
  40.         std::cin >> u >> v;
  41.         e[u].push_back(v), e[v].push_back(u);
  42.     }
  43.     dfs(1, 0), g[1] = now, now += len[1], dp(1, 0);
  44.     for (int i = 1; i <= n; i++) std::cout << ans[i] << "\n";
  45. }
  47. int main() {
  48.      // input(Test), output(Test);
  49.   std::cin.tie(nullptr)->sync_with_stdio(false);
  50.     int _ = 1;
  51.     // std::cin >> _;
  52.     while (_--) solve();
  53.     return 0;
  54. }
复制代码
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

使用道具 举报
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册
发帖
庇床铍
昨天 21:01

0

粉丝关注

11

主题发布

板块介绍填写区域，请于后台编辑
微信扫一扫