Kingdom‘s Power(2020CCPC秦皇岛)(树)

文章目录

• Kingdom's Power(2020CCPC秦皇岛)

Kingdom’s Power(2020CCPC秦皇岛)

题目大意

有一棵根节点为1的树，根节点处有无限个部队，每次操作你能让一个部队移动一步，问你最少移动多少次可以遍历完这个树。

解题思路

感觉这个题很有意思，我们首先可以计算出每个节点到根节点的距离和这个节点到最远的叶子节点的距离，在我们计算的时候先计算该节点的最短的叶子节点。然后看看是从更节点新派来个部队快还是，从另一个节点过来快。

比如这个图，我们先进行一次dfs，分别求出来到更节点的距离和到最远的根节点的距离，然后将每个子节点按照从短到长排序~也就是按照 max_deep从小到大排序~。
这个题最巧妙的就是用了一个 pre[] 数组记录上个链的最远距离。
假如现在我们dfs到 三号节点了。我们先初始化 pre[3]=3;
然后遍历 4号节点 通过比较， 是直接走到它快还是从 pre节点回来走到他快。
之后更新pre[3]=pre[4];
这样我们很好做到了，每次是从左边回到上来再走过去的问题了。
直接走到这个节点的距离就是 deep[x] 从左边走过来的时间就是 deep[pre[u]]-deep[u]+1;
至于如何记录花费的时间就看代码吧。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fast ios::sync_with_stdio(0);
const int mx=1000010;

vector<int> ve[mx];
int pre[mx];
int deep[mx],max_deep[mx];
ll ans;
void dfs(int u,int fa){
	deep[u]=deep[fa]+1;
	max_deep[u]=deep[u];
	for(int v:ve[u]){
		if(v!=fa){
			dfs(v,u);
			//更新到 距离它最远的叶子节点是多少 
			max_deep[u]=max(max_deep[u],max_deep[v]);
		}
	}
}
ll dfs2(int u,int fa){
	pre[u]=u;
	for(int v:ve[u]){
		if(v==fa) continue;
	// 统计最小的步数 
		ans+=min(deep[u],deep[pre[u]]-deep[u]+1);
		dfs2(v,u);
// 这一步真的是非常的巧妙！！！		
		pre[u]=pre[v];
	}
}

int main(){
	fast;
	int T,n;
	cin>>T;
	for(int ca=1;ca<=T;ca++){
		cin>>n;
		ans=0;
		for(int i=2,x;i<=n;i++){
			cin>>x;
			ve[x].push_back(i);
			ve[i].push_back(x);
		}
		cout<<"Case #"<<ca<<": ";
		dfs(1,0);
		// 从小到大排序 
		for(int i=1;i<=n;i++){
			sort(ve[i].begin(),ve[i].end(),[](int q,int m){
				return max_deep[q]<max_deep[m];	
			});
		}
		dfs2(1,0);
		cout<<ans<<"\n";
		for(int i=1;i<=n;i++) ve[i].clear();
	}
	return 0;
}
/*

6
8
1
2 2 2
3 4 5
3
1 1
6
1 2 3 4 4
*/