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