2020CCPC秦皇岛 k Kingdom’s Power

题意：有无数个军队可以从树根1出发，每花费一个点可以让军队走一步，问遍历完整个树的最小花费。
思路：先记录每个节点的高度，用节点根据它子树的高度的高度来排序，然后节点的高度为子树的最高高度+1，然后类似树形dp，从上往下递归h和与从下往上走的值取min。最后把所以的根节点的值加起来。

#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int N=1000010;
typedef long long ll;
int n;
vector<pair<int,int>>v[N];
int geth(int u)
{
   
	int hh=0;
	if(!v[u].size())	return 1;
	for(int i=0;i<v[u].size();i++)
	{
   
		v[u][i].first=geth(v[u][i].second);
	}
	sort(v[u].begin(),v[u].end());
	return v[u].back().first+1;
}
int val[N];
int dfs(int u,int h,int V)
{
   
	val[u]=V;
	if(!v[u].size())	
	return 1;
	int t=V;
	for(int i=0;i<v[u].size();i++)
	{
   
		t=min(h,dfs(v[u][i].second,h+1,t+1));
	}
	return t+1;
}
int main()
{
   
	int t;
	scanf("%d",&t);
	int k=0;
	while(t--)
	{
   	
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			v[i].clear();
		for(int i=1;i<=n;i++)
			val[i]=0;
		for(int i=2;i<=n;i++)
		{
   
			int fa;
			scanf("%d",&fa);
			v[fa].push_back({
   0,i});
		}
		geth(1);
		dfs(1,0,0);
		ll ans=0;
		for(int i=1;i<=n;i++)
			if(!v[i].size())
			{
   
				ans+=val[i];
			// cout<<val[i]<<endl;
			}
		printf("Case #%d: ",++k);
		printf("%lld\n",ans);
	}
}