题目链接:http://acm.split.hdu.edu.cn/showproblem.php?pid=3534

题意:n 之后 n-1条边,l,r,w;求出树上的最长路径以及最长路径的条数。

//思路参考 http://www.cnblogs.com/a-clown/p/6010109.html    hdu2196

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define ll long long
const int maxn=1e5+;
const int INF=0x3f3f3f3f; struct Edge
{
int v,l;
int next;
} edge[maxn<<]; int head[maxn],k;
int ans,t;
int d[maxn],num[maxn]; void init()
{
k=;
memset(head,-,sizeof(head));
} void addedge(int u,int v,int l)
{
edge[k].v=v;
edge[k].l=l;
edge[k].next=head[u];
head[u]=k++; edge[k].v=u;
edge[k].l=l;
edge[k].next=head[v];
head[v]=k++;
} void dfs(int u,int p)
{
d[u]=;
num[u]=;
for(int i=head[u]; i!=-; i=edge[i].next)
{
int v=edge[i].v;
if(v==p) continue;
dfs(v,u);
int tmp=d[v]+edge[i].l;
if(tmp+d[u]>ans)
{
ans=tmp+d[u];
t=num[u]*num[v];
}
else if(tmp+d[u]==ans)
t+=num[u]*num[v];
if(tmp>d[u])
{
num[u]=num[v];
d[u]=tmp;
}
else if(tmp==d[u])
num[u]+=num[v];
}
} int main()
{
//freopen("in.txt","r",stdin);
int n;
while(scanf("%d",&n)==)
{
init();
int l,r,len;
for(int i=; i<n; i++)
{
scanf("%d%d%d",&l,&r,&len);
addedge(l,r,len);
} ans=-INF,t=;
dfs(,);
printf("%d %d\n",ans,t);
}
return ;
}

最新文章

  1. 很强大的HTML+CSS+JS面试题(附带答案)
  2. 如何在mac本上安装android sdk 避免被墙
  3. JavaScript 基础第九天(DOM第三天)
  4. spring中schedule注解的使用
  5. Python入门笔记(16):对文件的操作(2)
  6. Delphi开发Windows服务程序
  7. CSS基础知识学习笔记
  8. 让IE6下支持固定定位
  9. PHPMailer中文说明
  10. HDFS运行原理
  11. git使用(上)-----基本的方法
  12. Protostuff序列化分析
  13. JSON字符串转C#实体Class类
  14. WebService C#开发/调用
  15. 为什么QQ空间和QQ邮箱都是IE默认打开?
  16. 基于Disruptor并发框架的分类任务并发
  17. LeetCode 19 Remove Nth Node From End of List (移除距离尾节点为n的节点)
  18. STL容器基本功能与分类
  19. Linux内核分析6
  20. Django 中设置分页页码,只显示当前页以及左右两页

热门文章

  1. Git on Windows 一些问题
  2. Datalogic组网模式下通讯
  3. AVAudioPlayer
  4. Hibernate之lazy延迟加载
  5. js中typeof和instanceof
  6. Dijkstra 算法
  7. ubuntu系统theano和keras的安装
  8. KMP模板
  9. mySQL 中主键值自动增加
  10. 打印IP 来源