2020CCPC秦皇岛 k Kingdom’s Power

2020CCPC秦皇岛 k Kingdom’s Power

题意是说给定一颗以1为根的树，根节点处有无数个人，每一秒只能派一个人移动到他的相邻节点上，问最少需要多少秒才能使所有结点被访问过。

• 类似一个树形dp。
• 把每个结点的val，初始化为从根走到它的步数。
• 一个初步的想法是，要尽可能把走到叶子结点的人也利用起来，避免从根节点走浪费太多秒。
• 设想一种情况，当前深度为10的结点A存在2条子链，左边的长度为3，右边的长度为5，那么最优的走法是从当前结点走向左边，再由左边的叶子走向右边的叶子。
• 注意从左叶子回溯到A的时候，对应的步数不能直接更新为A的val，因为它只能被利用一次。因此对于一个结点，我们要按子树高度大小升序遍历。
• 对于某个结点，按照以上策略，往回回溯给出的值与它的最深的叶子有关，所以子树的高度应为它最高的子树h+1。

空间复杂度O(N)
时间复杂度O(nlogn)
跟CJH大佬一起口胡搞出来的思路

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
int val[maxn];
int fa[maxn];
vector<pair<int,int> > son[maxn];//height,NO
void init(int n){
    for(int i=1;i<=n;++i)
        son[i].clear();
}
int geth(int rt){
    if(son[rt].empty()) return 1;
    for(int i=0;i<son[rt].size();++i){
        son[rt][i].first=geth(son[rt][i].second);
    }
    sort(son[rt].begin(),son[rt].end());
    return son[rt].back().first+1;
}
int dfs2(int rt,int d,int v){
    val[rt]=v;
    if(son[rt].empty()) return 1;
    int t=v;
    for(int i=0;i<son[rt].size();++i){
        t=min(d,dfs2(son[rt][i].second,d+1,t+1));
    }
    return t+1;
}

int main(){
    // freopen("in.txt","r",stdin);
    // ios::sync_with_stdio(false);
    int t,n;
    scanf("%d",&t);
    for(int ca=1;ca<=t;++ca){
        scanf("%d",&n);
        init(n);
        for(int i=2;i<=n;++i){
            scanf("%d",fa+i);
            son[fa[i]].push_back({0,i});
        }
        geth(1);
        dfs2(1,0,0);
        ll ans=0;
        for(int i=1;i<=n;++i)
            if(son[i].empty())
                ans+=val[i];
        printf("Case #%d: %lld
",ca,ans);
    }
    return 0;
}