本文共 2312 字，大约阅读时间需要 7 分钟。
1、
2、题目大意：（参考）
给出一棵树，求每一个结点到其他结点的最远权值和，
对于结点u来说，他的最大权值和可能来自两个方向，一个是u作为根节点到其子节点的最大值，另一个是以u的父节点为根的树的最大权值和加上根节点到u的距离
假设存在这么一棵树
1
2 3
4 5 6
7
1是根节点，23是1的孩子，45是2的孩子，6是3的孩子，7是6的孩子
我们假设要求2的最大距离值，有两种状态，
1、2作为根节点，到其孩子的最大距离值
2、2作为选中的路径的子节点，选中的子树以2的父节点1为根节点的子树，我们可以看到以1为根节点的子树的最大值再加上1-2的距离就是所求，但是前提是选中的1结点为根的最大值的子树中不包含2，假设包含2这个结点，那么最大值就是以2为根的，
adj(v-u)表示v-u之间的距离
dp[v][2]=max(dp[u][2],dp[v][0]+adj(v-u)==dp[u][0]?dp[u][1]:dp[u][0])+adj(v-u)
dp[v][0]表示以v为根节点的子树的最大值
dp[v][1]表示以v为根节点的子树的次大值（第二大）
3、超时代码：
#include #define N 10005#include #include using namespace std;int dp[N][3];struct node{ int v; int w;};vector adj[N];void dfs1(int u){ //printf("*****%d\n",adj[u].size()); int biggest=0,bigger=0; for(int i=0;i =biggest) { bigger=biggest; biggest=tmp; } else if(tmp>bigger) { bigger=tmp; } } dp[u][0]=biggest; dp[u][1]=bigger;}void dfs2(int u){ for(int i=0;i
4、AC代码：
#include #include #include using namespace std;const int N = 1e4 + 5;struct Vertex{ int head;} V[N];struct Edge{ int v,w,next;} E[N];int top;void init(){ memset(V,-1,sizeof(V)); top = 0;}void add_edge(int u,int v,int w){ E[top].v = v; E[top].w = w; E[top].next = V[u].head; V[u].head = top++;}int dp[N][3];void dfs1(int u){ int biggest = 0 , bigger = 0; for(int i=V[u].head; ~i; i=E[i].next) { int v = E[i].v; dfs1(v); int tmp = dp[v][0]+E[i].w; if(biggest <= tmp) { bigger = biggest; biggest = tmp; } else if(bigger < tmp) bigger = tmp; } dp[u][0] = biggest; dp[u][1] = bigger;}void dfs2(int u){ for(int i=V[u].head; ~i; i=E[i].next) { int v = E[i].v; dp[v][2] = max(dp[u][2] , dp[v][0]+E[i].w==dp[u][0] ? dp[u][1] : dp[u][0]) + E[i].w; dfs2(v); }}int main(){ int n; while(~scanf("%d",&n)) { init(); for(int v=2; v<=n; v++) { int u,w; scanf("%d%d",&u,&w); add_edge(u,v,w); } dfs1(1); dp[1][2] = 0; dfs2(1); for(int i=1; i<=n; i++) printf("%d\n",max(dp[i][0],dp[i][2])); } return 0;}
转载地址：http://brddi.baihongyu.com/