Submit StatusDescription 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又是一個很經典的樹狀dp,在這題裡，意思就是，結一個樹，把每個結點到其他結點的最大距離輸出來，我們先明確三個概念，第一長距離，是指，該結點通過子結點中的點能達到的最長距離，第二長距離是指，通過子結點通達到的剛好比第一長距離小一點點，也就是排第二長的距離，父結點的距離，指必須通過父結點，可以到達的最長距離我們以這個例子來說，我們可以從葉到根先找到最長和第二長，再通過從根到葉，最長和第二長所經由的路找到通過父結點，所能達到的最長距離，而最終的結果，一定是最長和父結點距離中的最大值所確定的，你畫圖就知道，最長路不是通過子結點中的，就是父結點中的最大值５１ ４１ １３ ３３ ６這個情況基本上把所有容易掉的情況展顯了，其中4 5號結點是最特殊的，４號結點，必須通過父結點達到最大５號必須通過父結點的達到最大
#include <iostream> #include <stdio.h> #include <vector> #include<string.h> using namespace std; struct computertree{int next ,val ;}; vector <computertree> vec[10050]; int n; int firstpath[10050];//分別記錄，當前結點的，第一長和第二長的距離通過的子結點的編號 int dp[10050],dpsecond[10050],dpfather[10050];//分別記錄第一長，第二長，和從父結點過來的最長的距離 int fmax(int a,int b) { if(a>b) return a; return b; } void init() { int i,e; computertree temp; memset(dp,0,sizeof(dp)); memset(dpsecond,0,sizeof(dpsecond)); memset(dpfather,0,sizeof(dpfather)); memset(firstpath,-1,sizeof(firstpath)); for(i=1;i<=n;i++) { vec[i].clear(); } for(i=2;i<=n;i++) { scanf("%d%d",&e,&temp.val); temp.next=i; vec[e].push_back(temp); } } void dfsup(int x)//從葉子結點向根來建樹,得到，最大，和第二大的距離 { int i,j; int flag1=-1,flag2=-1,maxx;//標記所取最長距離的點 if(vec[x].size()==0)//達到葉子結點返回 return ; for(i=0;i<vec[x].size();i++) { j=vec[x][i].next; dfsup(j);//不斷的向子結點進，直到達到了葉子結點 if(dp[j]+vec[x][i].val>dp[x]) { dp[x]=dp[j]+vec[x][i].val; flag1=j;//標記最大距離通向的結點 } } firstpath[x]=flag1; for(i=0;i<vec[x].size();i++) { j=vec[x][i].next; if(j!=flag1&&dp[j]+vec[x][i].val>dpsecond[x])//和第一不相等的子結點，就是第二大的子結點 { dpsecond[x]=dp[j]+vec[x][i].val ;//更新第二長的距離的大小 flag2=i; } } } void dfsdown(int x)//從根結點，向下進行更新，獲取最大值 { int i,j,tempval; for( i=0;i<vec[x].size();i++) { j=vec[x][i].next; tempval=vec[x][i].val; if(firstpath[x]!=j)//父結點的最長路不經過子結點，且距離大於子結點的最長路，就要進行更新 { dpfather[j]=fmax(dpfather[x],dp[x])+tempval;//對應４號結點情況 } else if(firstpath[x]==j) { dpfather[j]=fmax(dpfather[x],dpsecond[x])+tempval;//注意１對應５號結點 } dfsdown(j);//向子結點擴展 } } int main() { int i; while(scanf("%d",&n)!=EOF) { init(); dfsup(1); dfsdown(1); for(i=1;i<=n;i++) { printf("%d\n",fmax(dpfather[i],dp[i])); } } return 0; } #include <iostream>
#include <stdio.h>
#include <vector>
#include<string.h>
using namespace std;
struct computertree{int next ,val ;};
vector <computertree> vec[10050];
int n;
int firstpath[10050];//分別記錄，當前結點的，第一長和第二長的距離通過的子結點的編號
int dp[10050],dpsecond[10050],dpfather[10050];//分別記錄第一長，第二長，和從父結點過來的最長的距離
int fmax(int a,int b)
{
if(a>b)
return a;
return b;
}
void init()
{
int i,e;
computertree temp;
memset(dp,0,sizeof(dp));
memset(dpsecond,0,sizeof(dpsecond));
memset(dpfather,0,sizeof(dpfather));
memset(firstpath,-1,sizeof(firstpath));
for(i=1;i<=n;i++)
{
vec[i].clear();
}
for(i=2;i<=n;i++)
{
scanf("%d%d",&e,&temp.val);
temp.next=i;
vec[e].push_back(temp);
}
}
void dfsup(int x)//從葉子結點向根來建樹,得到，最大，和第二大的距離
{
int i,j;
int flag1=-1,flag2=-1,maxx;//標記所取最長距離的點
if(vec[x].size()==0)//達到葉子結點返回
return ;
for(i=0;i<vec[x].size();i++)
{
j=vec[x][i].next;
dfsup(j);//不斷的向子結點進，直到達到了葉子結點
if(dp[j]+vec[x][i].val>dp[x])
{
dp[x]=dp[j]+vec[x][i].val;
flag1=j;//標記最大距離通向的結點
}
}
firstpath[x]=flag1;
for(i=0;i<vec[x].size();i++)
{
j=vec[x][i].next;
if(j!=flag1&&dp[j]+vec[x][i].val>dpsecond[x])//和第一不相等的子結點，就是第二大的子結點
{
dpsecond[x]=dp[j]+vec[x][i].val ;//更新第二長的距離的大小
flag2=i;
}
}
}
void dfsdown(int x)//從根結點，向下進行更新，獲取最大值
{
int i,j,tempval;
for( i=0;i<vec[x].size();i++)
{
j=vec[x][i].next;
tempval=vec[x][i].val;
if(firstpath[x]!=j)//父結點的最長路不經過子結點，且距離大於子結點的最長路，就要進行更新
{
dpfather[j]=fmax(dpfather[x],dp[x])+tempval;//對應４號結點情況
}
else if(firstpath[x]==j)
{
dpfather[j]=fmax(dpfather[x],dpsecond[x])+tempval;//注意１對應５號結點
}
dfsdown(j);//向子結點擴展
}
}
int main()
{
int i;
while(scanf("%d",&n)!=EOF)
{
init();
dfsup(1);
dfsdown(1);
for(i=1;i<=n;i++)
{
printf("%d\n",fmax(dpfather[i],dp[i]));
}
}
return 0;
}
