[CF1009F] Dominant Indices - 树上启发式合并,map

[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;
}