好贷网好贷款

hdu2196 Computer

发布时间:2016-12-3 12:43:09 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"hdu2196 Computer",主要涉及到hdu2196 Computer方面的内容,对于hdu2196 Computer感兴趣的同学可以参考一下。

求树的所有结点的最长直径#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define M 10010 int len[M],len2[M],leaf[M],leaf2[M],head[M]; int n,tot; struct node{ int to,dis,next; }edge[M*2]; void insert(int u,int v,int dis){ edge[tot].to=v; edge[tot].dis=dis; edge[tot].next=head[u]; head[u]=tot++; } void dfs(int u,int pre){ int i,v; for(i=head[u];i!=-1;i=edge[i].next){ v=edge[i].to; if(v==pre) continue; dfs(v,u); if(len[v]+edge[i].dis>len[u]){ len2[u]=len[u]; leaf2[u]=leaf[u]; len[u]=len[v]+edge[i].dis; leaf[u]=v; } else if(len[v]+edge[i].dis>len2[u]){ len2[u]=len[v]+edge[i].dis; leaf2[u]=v; } } } void dfs2(int u,int pre){ int i,v; for(i=head[u];i!=-1;i=edge[i].next){ v=edge[i].to; if(v==pre) continue; if(leaf[u]==v){ if(len2[u]+edge[i].dis>len[v]){ len2[v]=len[v]; leaf2[v]=leaf[v]; len[v]=len2[u]+edge[i].dis; leaf[v]=u; } else if(len2[u]+edge[i].dis>len2[v]){ len2[v]=len2[u]+edge[i].dis; leaf2[v]=u; } } else{ if(len[u]+edge[i].dis>len[v]){ len2[v]=len[v]; leaf2[v]=leaf[v]; len[v]=len[u]+edge[i].dis; leaf[v]=u; } else if(len[u]+edge[i].dis>len2[v]){ len2[v]=len[u]+edge[i].dis; leaf2[v]=u; } } dfs2(v,u); } } int main(){ int v,dis; while(scanf("%d",&n)!=EOF){ tot=0; memset(head,-1,sizeof(head)); memset(len,0,sizeof(len)); memset(len2,0,sizeof(len2)); memset(leaf,-1,sizeof(leaf)); for(int i=2;i<=n;i++){ scanf("%d%d",&v,&dis); insert(i,v,dis); insert(v,i,dis); } dfs(1,-1); dfs2(1,-1); for(int i=1;i<=n;i++) printf("%d\n",len[i]); } return 0; }

上一篇:图片查看器、网页源码查看器
下一篇:Xcode 4.1~4.6 + iOS 5、iOS 6免证书(iDP)开发+真机调试+生成IPA全攻略

相关文章

关键词: hdu2196 Computer

相关评论