首页 > 代码库 > 【树形dp】Computer

【树形dp】Computer

2024-11-14 11:06:39   203人阅读

Computer

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 7324    Accepted Submission(s): 3627

Problem Description
A school bought the first computer some time ago(so this computer‘s id is 1). During the recent years the school bought N-1 new computers. Each new computer was connected to one of settled earlier. Managers of school are anxious about slow functioning of the net and want to know the maximum distance Si for which i-th computer needs to send signal (i.e. length of cable to the most distant computer). You need to provide this information.
技术分享


Hint: the example input is corresponding to this graph. And from the graph, you can see that the computer 4 is farthest one from 1, so S1 = 3. Computer 4 and 5 are the farthest ones from 2, so S2 = 2. Computer 5 is the farthest one from 3, so S3 = 3. we also get S4 = 4, S5 = 4.
 
Input
Input file contains multiple test cases.In each case there is natural number N (N<=10000) in the first line, followed by (N-1) lines with descriptions of computers. i-th line contains two natural numbers - number of computer, to which i-th computer is connected and length of cable used for connection. Total length of cable does not exceed 10^9. Numbers in lines of input are separated by a space.
 
Output
For each case output N lines. i-th line must contain number Si for i-th computer (1<=i<=N).
 
Sample Input
5
1 1
2 1
3 1
1 1
 
Sample Output
3
2
3
4
4
 
Author
scnu
 
Recommend
lcy
 
题目大意：给定N个点的无根树，求每个点到它最远点的距离。
试题分析：设dp[i]表示i到最远点的距离，我们发现dp[i]=max(dp[i->son]+1,dp[fa[i]]+1)
　　　　　但是这个转移方程在父节点的最长路如果是走到i的子树的那么就出错了。
　　　　　于是我们添加一维状态:dp[i][2] 表示i号节点的子树中最远点与不在子树中最远点。
　　　　　dp[i][0]=max(dp[i->son][0]+1)
　　　　　dp[i][1]=max(dp[fa[i]][1]+1,dp[fa[i]][0]+1)
　　　　　列出转移方程，发现我们的顾虑并没有消除，我们不确定父节点的在子树中最大的是不是i的子树。
　　　　　为了解决这个问题，我们将状态变成dp[i][3]表示i到子树中最远点，i到子树中次远点，不在i的子树中与i距离最远的点
　　　　　那么dp[i][0]=max(dp[i->son][0]+1)
　　　　　　　dp[i][1]=max(dp[i->son][0]+1)  (i->son不满足max(dp[i->son][0]))
　　　　　　　dp[i][2]=max(dp[fa[i]][2]+1,dp[fa[i]][0]+1) (dp[fa[i]][0]的节点不在i的子树中)
　　　　　　　　　　   max(dp[fa[i]][2]+1,dp[fa[i]][1]+1) (如果在就要退而求其次了)
 
代码：
#include<iostream>#include<cstring>#include<cstdio>#include<vector>#include<queue>#include<stack>#include<algorithm>using namespace std;inline int read(){	int x=0,f=1;char c=getchar();	for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1;	for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘;	return x*f;}const int MAXN=20001;const int INF=999999;int N,M; int len[MAXN];vector<int> vec[MAXN];struct data{    int Son,k;}dp[MAXN][3];int fap[MAXN];int ans=0;void dfs(int x,int fa){	for(int i=0;i<vec[x].size();i++){		if(vec[x][i]!=fa) dfs(vec[x][i],x);	}	for(int i=0;i<vec[x].size();i++){		int son=vec[x][i];		if(son==fa) continue;		if(dp[x][0].k<dp[son][0].k+len[son]) dp[x][0].k=dp[son][0].k+len[son],dp[x][0].Son=son;	}	for(int i=0;i<vec[x].size();i++){		int son=vec[x][i];		if(son==fa||son==dp[x][0].Son) continue;		if(dp[x][1].k<dp[son][0].k+len[son]) dp[x][1].k=dp[son][0].k+len[son];	}}void dfs2(int x,int fa){	if(fa!=-1){	    dp[x][2].k=dp[fap[x]][2].k+len[x];		if(dp[fap[x]][0].Son!=x) dp[x][2].k=max(dp[x][2].k,dp[fap[x]][0].k+len[x]);		else dp[x][2].k=max(dp[x][2].k,dp[fap[x]][1].k+len[x]);	}	for(int i=0;i<vec[x].size();i++){		if(vec[x][i]!=fa) dfs2(vec[x][i],x);	}	return ;}int main(){	while(scanf("%d",&N)!=EOF){		for(int i=1;i<=N;i++){			dp[i][0].k=dp[i][1].k=dp[i][2].k=0;			dp[i][0].Son=dp[i][1].Son=0;			vec[i].clear(); fap[i]=0;			len[i]=0;		}		for(int i=2;i<=N;i++){			int fat=read(),ltg=read();			vec[fat].push_back(i);			len[i]=ltg; fap[i]=fat;		}		dfs(1,-1);dfs2(1,-1);		for(int i=1;i<=N;i++) cout<<max(dp[i][0].k,dp[i][2].k)<<endl;	}}

【树形dp】Computer


联系
我们