专栏文章
2025勰码公益营 B 班 37号 作业 1-3
个人记录参与者 1已保存评论 0
文章操作
快速查看文章及其快照的属性,并进行相关操作。
- 当前评论
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @miqao3es
- 此快照首次捕获于
- 2025/12/04 01:42 3 个月前
- 此快照最后确认于
- 2025/12/04 01:42 3 个月前
CF1009F Dominant Indices 题解
题目大意
给一棵 个点的以 为根的树,对每个点求最小的 使得其子树中到它距离为 (边权为 )的点最多。
。
思路
因为有根,所以点分治不行。
那么还有什么算法适合这类问题呢?dsu on tree。
实现
我们开一个全局桶 ,用 维护桶中出现最多的数的出现次数,用 维护桶中最小的出现最多的数(这些均可在插入时 求),然后跑 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;
}
相关推荐
评论
共 0 条评论,欢迎与作者交流。
正在加载评论...