http://www.cnblogs.com/kuangbin/archive/2012/08/28/2659915.html

?

求每個節(jié)點(diǎn)到葉子節(jié)點(diǎn)的最長距離

?

需要保存每個節(jié)點(diǎn)到葉子節(jié)點(diǎn)距離的最大值和次大值。第一次dfs求出到下面葉子節(jié)點(diǎn)的最大值，第二次dfs更新從父節(jié)點(diǎn)過來的最大值。

?

#include <iostream> #include <string> #include <cstring> #include <cstdlib> #include <cstdio> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <cctype> #include <vector> #include <iterator> #include <set> #include <map> #include <sstream> using namespace std;#define mem(a,b) memset(a,b,sizeof(a)) #define pf printf #define sf scanf #define spf sprintf #define pb push_back #define debug printf("!\n") #define MAXN 20000+5 #define MAX(a,b) a>b?a:b #define blank pf("\n") #define LL long long #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) #define pqueue priority_queue #define INF 0x3f3f3f3f#define ls (rt<<1) #define rs (rt<<1|1)int n,m;int ptr = 1,head[MAXN],a[MAXN],dp[MAXN][2],vis[MAXN];int mx[MAXN],mx2[MAXN],vx[MAXN],vx2[MAXN];struct node {int y,val,next; }tree[MAXN];void add(int fa,int son,int val) {tree[ptr].y = son;tree[ptr].val = val;tree[ptr].next = head[fa];head[fa] = ptr++; }void cg(int &x,int &y) {int tmp = x;x = y;y = tmp; }void dfs(int root,int fa) {for(int i=head[root];i!=-1;i=tree[i].next){int y = tree[i].y;if(y == fa) continue;dfs(y,root);if(mx2[root] < mx[y]+tree[i].val){mx2[root] = mx[y]+tree[i].val;vx2[root] = y;if(mx2[root]>mx[root]){swap(mx[root],mx2[root]);swap(vx[root],vx2[root]);}}} }void dfs2(int root,int fa) {for(int i=head[root];i!=-1;i=tree[i].next){int y = tree[i].y;if(y == fa) continue;if(y == vx[root]){if(tree[i].val + mx2[root] > mx2[y]){mx2[y] = tree[i].val + mx2[root];vx2[y] = root;if(mx2[y]>mx[y]){swap(mx[y],mx2[y]);swap(vx[y],vx2[y]);}}}else{if(tree[i].val + mx[root] > mx2[y]){mx2[y] = tree[i].val + mx[root];vx2[y] = root;if(mx2[y]>mx[y]){swap(mx[y],mx2[y]);swap(vx[y],vx2[y]);}}}dfs2(y,root);} }int main() {int i,j,t,kase=1;while(~sf("%d",&n)){mem(tree,0);mem(head,-1);mem(mx,0);mem(mx2,0);mem(vx,0);mem(vx2,0);ptr = 1;int x,y;for(i=2;i<=n;i++){sf("%d%d",&x,&y);add(x,i,y);add(i,x,y);}dfs(1,-1);dfs2(1,-1);for(i=1;i<=n;i++) pf("%d\n",mx[i]);}return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/qlky/p/5774759.html

總結(jié)

以上是生活随笔為你收集整理的hdu 2196 叶子节点最长距离（树DP）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。