首页 > 代码库 > hdu2196(树形dp)
hdu2196(树形dp)
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2196
题意：一个有N个结点的树，给你相邻两个结点的距离，问你对于第i个结点，树中离i最远的结点的距离是多少。
分析：因为树上任意某个节点到树上任意节点的最远距离的端点一定会是树上直径的两个端点之一。（树的直径为树上距离最大的两个点组成）。因此由任意选个点根据最大值dfs求出树的直径的一个断点，再从端点出发dfs求出另外个端点，再从另个端点dfs扫一遍。那么由树的直径的两个端点扫过后的每个点距离就是最大距离。
#include <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <stack>#include <vector>#include <set>#include <map>#define LL long long#define mod 1000000007#define inf 0x3f3f3f3f#define N 10010#define clr(a) (memset(a,0,sizeof(a)))using namespace std;struct edge{ int next,v,w; edge(){} edge(int v,int w,int next):v(v),w(w),next(next){}}e[N*2];int dp[N],head[N],tot,n,st,mx;void addedge(int u,int v,int w){ e[tot]=edge(v,w,head[u]); head[u]=tot++;}void dfs(int u,int fa,int sum){ if(sum>=mx)mx=sum,st=u; for(int i=head[u];~i;i=e[i].next) { int v=e[i].v; if(v==fa)continue; dp[v]=max(sum+e[i].w,dp[v]); dfs(v,u,sum+e[i].w); }}int main(){ int u,v; while(scanf("%d",&n)>0) { clr(dp);tot=0; memset(head,-1,sizeof(head)); for(int i=2;i<=n;i++) { scanf("%d%d",&u,&v); addedge(i,u,v); addedge(u,i,v); } mx=0; dfs(1,0,0); dfs(st,0,0); dfs(st,0,0); for(int i=1;i<=n;i++)printf("%d\n",dp[i]); }}
hdu2196(树形dp)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。