ComputerTime Limit: 1000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 2683Accepted Submission(s): 1375
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
51 12 13 11 1
Sample Output
32344
Author
scnu
嗯哼，捕获树形DP练手题一只~
这个嘛，由于刚学C++和树形DP，码起题来很生疏，但这题码起来可是相当酣畅！
第一次用class和vector，就是为了让程序漂亮一点。思路是看别人的题解的，代码是自己打的，但是后来离奇地发现竟然有大牛的程序连变量名都和我一样……（莫名高兴！）
这题写完飞快，一遍AC，权当纪念！
下面是题解：
此题大意（HDU的英文题读起来就是比poj舒服）：
学校买来一堆电脑，编号1~N，一些电脑之间有连线，求每只电脑到其他电脑的最大距离。
例如上图，1号电脑到4号距离最长为3，所以S1=3；2号电脑到5号和4号电脑的距离最长为2，，所以S2=2；以此类推，输出S1~Sn
输入格式：
第一行一个 N
接下来N-1行每行两个整数fa、dis
分别表示2~N号电脑的父节点及它到父节点的距离
输出格式：
共N行，S1~Sn
（每个测试点有多组数据）
思路：根节点的S显然是max{叶子节点到根的距离}
其他节点的S有两种情况：①这条路在以该节点为根的子树内
②这条路在以该节点为根的子树外
于是我们定义
len[ i ]表示节点 i 到其父节点的距离
DP[ i ].longest表示以节点 i 为根的子树中的最长路
DP[ i ].second表示以节点 i 为根的子树中的次长路（这个描述有点不准确，应该是与longest始于 i 的不同儿子节点的最长路）
DP[ i ].ID表示以节点 i 为根的子树中的最长路中 i 的后继结点（即这条路包含 i 的哪一个儿子）
dp[ i ]表示以节点 i 为根的子树外的最长路
vector<int> list存储邻接表
好了，有了上面这一坨定义以后一切都迎刃而解，自底向上解决DP数组，再自顶向下解决dp数组（状态转移方程直接边写代码边 y y 啦，谁都看得懂的啦~ 这题就是纪念一下的啦~）
#include<cstdio>#include<vector>#define BIG [10005]using namespace std;class lala{public:int longest,second,ID;void pre(){longest=second=ID=0;}};vector<int>list BIG;lala DP BIG;int i,n,fa,dp BIG,len BIG;inline int max(int x,int y){return x>y?x:y;}inline void dfs_up(int root){int son,tot=list[root].size();for(int i=0;i<tot;++i){son=list[root][i];dfs_up(son);if (DP[son].longest+len[son]>DP[root].longest){DP[root].longest=DP[son].longest+len[son];DP[root].ID=son;}}for(int i=0;i<tot;++i){son=list[root][i];if((son!=DP[root].ID)&&(DP[son].longest+len[son]>DP[root].second))DP[root].second=DP[son].longest+len[son];}}inline void dfs_down(int root){int son,tot=list[root].size();for(int i=0;i<tot;++i){son=list[root][i];if (son!=DP[root].ID)dp[son]=max(DP[root].longest,dp[root])+len[son];elsedp[son]=max(DP[root].second,dp[root])+len[son];dfs_down(son);}}int main(){while(~scanf("%d",&n)){for(i=0;i<=n;++i){DP[i].pre();dp[i]=0;list[i].clear();}for(i=2;i<=n;++i){scanf("%d%d",&fa,&len[i]);list[fa].push_back(i);}dfs_up(1);dfs_down(1);for(i=1;i<=n;++i)printf("%d\n",max(dp[i],DP[i].longest));}return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。
我们人生中最大的懒惰，就是当我们明知自己拥有作出选择的能力，
