80求条
  • 板块P10962 Computer
  • 楼主ETGX
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/11/25 21:34
  • 上次更新2024/11/26 10:42:56
查看原帖
80求条
1413092
ETGX楼主2024/11/25 21:34
#include <bits/stdc++.h>
using namespace std;
int n,dp[10000][3];
struct gcex{
	int x,l;
};
vector <gcex> computers[10000];
void dfs1(int u,int fa){
	for(int i=0;i<computers[u].size();i++){
		int v=computers[u][i].x;
		if(v!=fa){
			dfs1(v,u);
			if(dp[v][0]+computers[u][i].l>dp[u][0]){
				dp[u][1]=dp[u][0];
				dp[u][0]=dp[v][0]+computers[u][i].l;
			}
			else{
				dp[u][1]=max(dp[u][1],dp[v][0]+computers[u][i].l);
			}
		}
	}
}
void dfs2(int u,int fa){
	for(int i=0;i<computers[u].size();i++){
		int v=computers[u][i].x;
		if(v!=fa){
			if(dp[v][0]+computers[u][i].l==dp[u][0]){
				dp[v][2]=max(dp[u][2],dp[u][1])+computers[u][i].l;
			}
			else{
				dp[v][2]=max(dp[u][2],dp[u][0])+computers[u][i].l;
			}
			dfs2(v,u);
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<n;i++){
		int a,b;cin>>a>>b;
		computers[i].push_back({a-1,b});
		computers[a-1].push_back({i,b});
	}
	dfs1(0,-1);
	dfs2(0,-1);
	for(int i=0;i<n;i++){
		cout<<max(dp[i][0],dp[i][2])<<endl;
	}
}
2024/11/25 21:34
加载中...