「Gym 102759I」Query On A Tree 17

题目大意

给定一颗 \(N\) 个节点以 \(1\) 为根的有根树，每次给以 \(u\) 为根的子树每点加 \(1\) 的值或给路径 \(u - v\) 上每点加 \(1\) 的值，每次修改后查询一个点 \(u\) 使得 \(\sum_{v = 1}^N dis(u, v)\) 最小。
题目转换

首先我们很贪心地想到点 \(u\) 是树的带权重心，证明如下：
假设点 \(u\) 是带权重心，\(sum_u\) 为 \(u\) 的子树权值和，另取一点 \(v (v \neq u)\)，令 \(u\) 为根，则对在路径 \(u - v\) 上每一点 \(p (p \neq u)\) 有

\[\sum_{i = 1}^N dis(i, p) - \sum_{i = 1}^N dis(i, fa_p) = N - 2sum_p \geq 0\]
所以从 \(u\) 到 \(v\) 的移动过程中每一步都不优，故 \(u\) 为我们的答案。
所以我们每次加子树，加路径，查带权重心。
然后再原树上带权重心 \(u\) 的子树权值和一定刚好严格大于整棵树权值和一半，否则一定不优，证明同上。换做 dfs 序，即一个区间权值和大于数列和一半。
做法详解

现在我们明确一下我们要求什么：找到一个深度最深的点 \(u\) 使得在 dfs 序下 \([dfn_u, dfn_u + siz_u - 1]\) 的权值和严格大于 \([1, n]\) 的权值和。
考虑怎么去找，我们先要猜个结论，设 \(pre_i\) 表示在 dfs 序下的权值前缀和，再找到一个 \(j\) 使得 \(pre_{j - 1}, pre_n - pre_j \leq \left \lfloor pre_n \right \rfloor\)，则我们找到的点 \(u\) 一定满足 \(j \in [dfn_u, dfn_u + siz_u - 1]\) ,为什么呢？很简单，我们的 \([dfn_u, dfn_u + siz_u - 1]\) 权值和大于总权值一半，而无论是 \(pre_{j - 1}\) 还是 \(pre_n - pre_j\) 即 \(j\) 的左右两边都小于总权值一半，所以我们的区间一定不会被包含于 \([1, j - 1]\) 或 \([j + 1, n]\) ，故 \(rnk_j\) (dfs 序为 \(j\) 的结点) 一定在 \(u\) 的子树中。
\(rnk_j\) 很好找，然后我们因为要找深度最深的那个满足条件的点，且子树和满足单调性，所以满足条件的点一定是在树上连续的，故考虑倍增，每次check跳上去的点是否不满足要求，若是，则跳，反之不跳，最后再跳 \(1\) 步（如果 \(rnk_j\) 满足条件就不管）得到答案 \(u\)。
Solution

挺好实现的，思路清晰，大多都是模板，就是代码微长（也就百来行）。

1. /*
2. address:https://vjudge.net/problem/Gym-102759I
3. AC 2025/10/28 20:29
4. */
5. #include<bits/stdc++.h>
6. using namespace std;
7. typedef long long LL;
8. const int N = 1e5 + 5;
9. int dfn[N], siz[N], top[N], son[N], fa[N], dep[N], rnk[N];
10. int cntn;
11. vector<int>G[N];
12. int n, q;
13. struct SegmentTree {
14. #define ls (id << 1)
15. #define rs (id << 1 | 1)
16. #define mid (l + r >> 1)
17.     LL sum[N << 2], add[N << 2];
18.     inline void pushup(int id) { sum[id] = sum[ls] + sum[rs]; }
19.     inline void pushdown(int id, int l, int r) {
20.         if (add[id]) {
21.             add[ls] += add[id];
22.             add[rs] += add[id];
23.             sum[ls] += add[id] * (mid - l + 1);
24.             sum[rs] += add[id] * (r - mid);
25.             add[id] = 0;
26.         }
27.     }
28.     inline void modify(int id, int l, int r, int L, int R) {
29.         if (l >= L && R >= r) {
30.             sum[id] += r - l + 1;
31.             ++add[id];
32.             return;
33.         }
34.         pushdown(id, l, r);
35.         if (L <= mid) modify(ls, l, mid, L, R);
36.         if (R > mid) modify(rs, mid + 1, r, L, R);
37.         pushup(id);
38.     }
39.     inline LL query(int id, int l, int r, int L, int R) {
40.         if (l >= L && R >= r) return sum[id];
41.         pushdown(id, l, r);
42.         LL ret = 0;
43.         if (L <= mid) ret += query(ls, l, mid, L, R);
44.         if (R > mid) ret += query(rs, mid + 1, r, L, R);
45.         return ret;
46.     }
47.     inline int search(int id, int l, int r, LL k) {
48.         if (l == r) return sum[id] <= k ? l : l - 1;
49.         pushdown(id, l, r);
50.         if (sum[ls] <= k) return search(rs, mid + 1, r, k - sum[ls]);
51.         else return search(ls, l, mid, k);
52.     }
53. }SGT;
54. const int K = 20;
55. int up[K][N];
56. inline void dfs1(int u) {
57.     dep[u] = dep[fa[u]] + 1;
58.     up[0][u] = fa[u];
59.     for (int i = 1;i < K;++i) up[i][u] = up[i - 1][up[i - 1][u]];
60.     siz[u] = 1;son[u] = 0;
61.     for (auto v : G[u])
62.         if (v != fa[u]) {
63.             fa[v] = u;
64.             dfs1(v);
65.             siz[u] += siz[v];
66.             if (siz[v] > siz[son[u]]) son[u] = v;
67.         }
68. }
69. inline void dfs2(int u) {
70.     dfn[u] = ++cntn;
71.     rnk[cntn] = u;
72.     if (!son[u]) return;
73.     top[son[u]] = top[u];
74.     dfs2(son[u]);
75.     for (auto v : G[u])
76.         if (v != son[u] && v != fa[u]) {
77.             top[v] = v;
78.             dfs2(v);
79.         }
80. }
81. LL sum;
82. inline void update(int u, int v) {
83.     while (top[u] != top[v]) {
84.         if (dep[top[u]] < dep[top[v]]) swap(u, v);
85.         SGT.modify(1, 1, n, dfn[top[u]], dfn[u]);
86.         sum += dfn[u] - dfn[top[u]] + 1;
87.         u = fa[top[u]];
88.     }
89.     if (dep[u] > dep[v]) swap(u, v);
90.     SGT.modify(1, 1, n, dfn[u], dfn[v]);
91.     sum += dfn[v] - dfn[u] + 1;
92. }
93. int main() {
94.     scanf("%d", &n);
95.     for (int i = 1;i < n;++i) {
96.         int u, v;scanf("%d%d", &u, &v);
97.         G[u].push_back(v);G[v].push_back(u);
98.     }
99.     dfs1(1);dfs2(1);
100.     scanf("%d", &q);
101.     while (q--) {
102.         int op, u;scanf("%d%d", &op, &u);
103.         if (op == 1) SGT.modify(1, 1, n, dfn[u], dfn[u] + siz[u] - 1), sum += siz[u];
104.         if (op == 2) {
105.             int v;scanf("%d", &v);
106.             update(u, v);
107.         }
108.         int p = SGT.search(1, 1, n, sum >> 1) + 1;
109.         u = rnk[p];
110.         for (int i = K - 1;i >= 0;--i)
111.             if (up[i][u] && SGT.query(1, 1, n, dfn[up[i][u]], dfn[up[i][u]] + siz[up[i][u]] - 1) <= sum >> 1) u = up[i][u];
112.         if (up[0][u] && SGT.query(1, 1, n, dfn[u], dfn[u] + siz[u] - 1) <= sum >> 1) u = up[0][u];
113.         printf("%d\n", u);
114.     }
115.     return 0;
116. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

谢谢分享，辛苦了

这个有用。