2025勰码公益营 B 班 37号 作业 1-3
porse
·
·
个人记录
CF1009F Dominant Indices 题解
题目大意
给一棵 n 个点的以 1 为根的树，对每个点求最小的 k 使得其子树中到它距离为 k（边权为 1）的点最多。
## 思路
因为有根，所以点分治不行。
那么还有什么算法适合这类问题呢？dsu on tree。
## 实现
我们开一个全局桶 $t$，用 $maxx$ 维护桶中出现最多的数的出现次数，用 $idx$ 维护桶中最小的出现最多的数（这些均可在插入时 $\mathcal{O}(1)$ 求），然后跑 dsu on tree 就行了。
## Code
```cpp
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 1000010;
int n, a, b, t[maxn], maxx, mindepp, depp[maxn], fa[maxn], hs[maxn], sz[maxn], ans[maxn];
vector <int> G[maxn];
void dfs(int u) { // 预处理树的基本信息
sz[u] = 1;
int maxx = 0;
for (int now : G[u]) {
if (now == fa[u]) continue;
fa[now] = u;
depp[now] = depp[u] + 1;
dfs(now);
sz[u] += sz[now];
if (sz[now] > maxx) {
maxx = sz[now];
hs[u] = now;
}
}
return ;
}
void add(int u) { // 加一个子树
t[depp[u]]++;
if (t[depp[u]] > maxx) { // 此时最大值、最小下标都必须更新
maxx = t[depp[u]];
mindepp = depp[u];
} else if (t[depp[u]] == maxx) { // 更新最小下标
mindepp = min(mindepp, depp[u]);
}
for (int now : G[u]) {
if (now == fa[u]) continue;
add(now);
}
return ;
}
void del(int u) { // 删一个子树
t[depp[u]]--;
for (int now : G[u]) {
if (now == fa[u]) continue;
del(now);
}
return ;
}
void solve(int u, bool save) { // dsu 的递归
for (int now : G[u]) {
if (now == fa[u] || now == hs[u]) continue;
solve(now, 0);
}
if (hs[u]) solve(hs[u], 1);
for (int now : G[u]) {
if (now == fa[u] || now == hs[u]) continue;
add(now);
}
t[depp[u]]++; // 别忘了加上本身
if (t[depp[u]] > maxx) {
maxx = t[depp[u]];
mindepp = depp[u];
} else if (t[depp[u]] == maxx) {
mindepp = min(mindepp, depp[u]);
}
ans[u] = mindepp - depp[u];
if (!save) {
mindepp = n + 1;
maxx = 0;
del(u);
}
return ;
}
signed main() {
ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
cin >> n;
for (int i = 1; i < n; i++) {
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
depp[1] = 1;
dfs(1);
mindepp = n + 1;
solve(1, 1); // 这里 save = 1 可以稍微省一点常数
for (int i = 1; i <= n; i++) {
cout << ans[i] << '\n';
}
return 0;
}
```