2020ccpc秦皇岛K题

就是给你一棵树，从1号根开始放无数个机器人，要机器人覆盖所有边的最小路径和；

可以树形DP但是没必要，假设只有一个机器人的时候，答案就是边数*2 - 根离最远的叶子的距离，两个机器人的时候就相当于把走过两次的边改成一次，牺牲一些边获取一些边，算贡献的方法；

具体可以看代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn = 1e6+11;
vector<int>G[maxn];
void add(int x,int y){
	G[x].push_back(y);
}
ll ans =0 ;
ll dp[maxn];
ll dep[maxn];




int dfs(int x,int fa,int d){
	dep[x] = d;                  
	for(int i=0;i<G[x].size();i++){
		int p = G[x][i];
		if(p == fa) continue;
		dfs(p,x,d+1);
		dp[x] = max(dp[x],dp[p]+1);
	}
	return 0;
}
bool bml(int a,int b){
	return dp[a] > dp[b];
}


int dfs2(int x,int fa,int flag){
	//flag==1不能计算
	
	sort(G[x].begin(),G[x].end(),bml);
	if(flag == 0){
		ans += min(dep[x] - dp[x] - 2,0LL);
	}
	
	int f = 0;
	for(int i=0;i<G[x].size();i++){
		int p = G[x][i];
		if(p == fa) continue;
		f++;
		if(f == 1){
			dfs2(p,x,1);
		}
		else{
			dfs2(p,x,0);
		}
	} 
	
	return 0;
}




int main(){
	
	
	int t;
	int aa = 0;
	scanf("%d",&t);
	while(t--){
		int n;
		scanf("%d",&n);
		for(int i=0;i<=n;i++){
			dep[i] = 0;
			dp[i] = 0;	
			G[i].clear();
		}
		
		for(int i=2;i<=n;i++){
			int x;
			scanf("%d",&x);
			add(x,i);
			add(i,x);
		}
		dfs(1,0,0);
		ans = (n-1)*2 - dp[1];
		
		dfs2(1,0,1);
		
		printf("Case #%d: %lld\n",++aa,ans);
		
		
	}
	return 0;
}

2020ccpc秦皇岛K题

推荐阅读