Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3526 Accepted Submission(s): 1788
树形DP、带注释
#include <iostream> #include <algorithm> #include <cstdio> #include <queue> #include <cmath> #include <map> #include <vector> #include <iterator> #include <cstring> #include <string> using namespace std; #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define INF 0x7fffffff #define ll long long #define N 10010 struct Edge { int to,next,len; }edge[N<<1]; int head[N],tot; int n; int dp[N][3]; //dp[i][0]表示从儿子能走的次大距离 //dp[i][1]表示从儿子能走的最大距离 //dp[i][2]表示从父亲能走的最大距离 template <class T> inline bool input(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!=‘-‘&&(c<‘0‘||c>‘9‘)) c=getchar(); sgn=(c==‘-‘)?-1:1; ret=(c==‘-‘)?0:(c-‘0‘); while(c=getchar(),c>=‘0‘&&c<=‘9‘) ret=ret*10+(c-‘0‘); ret*=sgn; return 1; } inline void out(int x) { if(x>9) out(x/10); putchar(x%10+‘0‘); } void init() { tot=0; memset(head,-1,sizeof(head)); memset(dp,0,sizeof(dp)); } void add(int x,int y,int z) { edge[tot].to=y; edge[tot].len=z; edge[tot].next=head[x]; head[x]=tot++; } void dfs1(int u) //从下往上、求出u到子树的最远距离和次远距离 { for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; int w=edge[i].len; dfs1(v); if(dp[v][1]+w>=dp[u][1]) { dp[u][0]=dp[u][1]; dp[u][1]=dp[v][1]+w; } else if(dp[v][1]+w>dp[u][0]) { dp[u][0]=dp[v][1]+w; } } } void dfs2(int u) //从上往下、求出从父亲、从儿子走的最长距离 { for(int i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].to; int w=edge[i].len; if(dp[u][1]==dp[v][1]+w) //如果v 在u的最长路上,那么两条路:从父亲U的父亲走,父亲U的最长儿子走 { dp[v][2]=max(dp[u][0],dp[u][2])+w; } else //如果v不在u的最长路上,那么两条路:从父亲U的父亲走,父亲U的次长儿子走 { dp[v][2]=max(dp[u][1],dp[u][2])+w; } dfs2(v); } } int main() { while(input(n)) { init(); for(int i=2;i<=n;i++) { int a,b; input(a); input(b); add(a,i,b); } dfs1(1); dfs2(1); for(int i=1;i<=n;i++) { out(max(dp[i][1],dp[i][2])); //取从儿子和从父亲能走的最大距离 putchar(‘\n‘); } } return 0; }
原文:http://www.cnblogs.com/hate13/p/4090411.html