[CF1009F] Dominant Indices - 树上启发式合并,map
Description
给定一棵以 (1) 为根的树。设 (d(u,x)) 为 (u) 子树中到 (u) 距离为 (x) 的节点数。对于每个点求一个最小的 (k) 使得 (d(u,k)) 最大。
Solution
树上启发式合并
首先脑补出的是比较传统的找重儿子然后用数据结构的写法
但这里可以实现得更加精巧,我们对每个点维护一个 map
表示他子树中各种深度的点的数量
(先停一下,脑补一下这样该怎么暴力合并怎么求答案)
好了,在此基础上加入启发式的操作,我们比较当前点和它所有孩子的 map
大小,把最大的那个 map
换过来(当然顺便要更新一下答案)
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000005;
int dep[N], ans[N], n;
vector<int> g[N];
map<int, int> mp[N];
void dfs(int p, int from)
{
dep[p] = dep[from] + 1;
mp[p][dep[p]]++;
ans[p] = dep[p];
for (int q : g[p])
if (q != from)
{
dfs(q, p);
if (mp[p].size() < mp[q].size())
{
swap(mp[p], mp[q]);
ans[p] = ans[q];
}
for (auto [dep_q, cnt_dep_q] : mp[q])
{
mp[p][dep_q] += cnt_dep_q;
if (mp[p][dep_q] + (dep_q < ans[p]) > mp[p][ans[p]])
{
ans[p] = dep_q;
}
}
}
}
signed main()
{
ios::sync_with_stdio(false);
cin >> n;
for (int i = 1; i < n; i++)
{
int t1, t2;
cin >> t1 >> t2;
g[t1].push_back(t2);
g[t2].push_back(t1);
}
dfs(1, 1);
for (int i = 1; i <= n; i++)
cout << ans[i] - dep[i] << endl;
}