专栏文章

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 题解

题目大意

给一棵 nn 个点的以 11 为根的树,对每个点求最小的 kk 使得其子树中到它距离为 kk(边权为 11)的点最多。
1n1061 \leqslant n \leqslant 10^6

思路

因为有根,所以点分治不行。
那么还有什么算法适合这类问题呢?dsu on tree。

实现

我们开一个全局桶 tt,用 maxxmaxx 维护桶中出现最多的数的出现次数,用 idxidx 维护桶中最小的出现最多的数(这些均可在插入时 O(1)\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;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...