[BZOJ3124]直径
2024-10-21 12:56:48
Description
小Q最近学习了一些图论知识。根据课本,有如下定义。树:无回路且连通的无向图,每条边都有正整数的权值来表示其长度。如果一棵树有N个节点,可以证明其有且仅有N-1 条边。 路径:一棵树上,任意两个节点之间最多有一条简单路径。我们用 dis(a,b)
表示点a和点b的路径上各边长度之和。称dis(a,b)为a、b两个节点间的距离。
直径:一棵树上,最长的路径为树的直径。树的直径可能不是唯一的。
现在小Q想知道,对于给定的一棵树,其直径的长度是多少,以及有多少条边满足所有的直径都经过该边。
Input
第一行包含一个整数N,表示节点数。
接下来N-1行,每行三个整数a, b, c ,表示点 a和点b之间有一条长度为c
的无向边。
Output
共两行。第一行一个整数,表示直径的长度。第二行一个整数,表示被所有
直径经过的边的数量。
Sample Input
6
3 1 1000
1 4 10
4 2 100
4 5 50
4 6 100
3 1 1000
1 4 10
4 2 100
4 5 50
4 6 100
Sample Output
1110
2
2
【样例说明】
直径共有两条,3 到2的路径和3到6的路径。这两条直径都经过边(3, 1)和边(1, 4)。
HINT
对于100%的测试数据:2≤N≤200000,所有点的编号都在1..N的范围内,
边的权值≤10^9。
就是让你求直径的长和直径并的数量。
直径当然好求,而直径并,一定是在一条直径上。
所以我们可以先求出一条最长链。而所有直径的并一定是最长链上连续的一段。
证明很简单:如果中间有分开而最后又和在一起,显然会形成一个环。
然后我们对于最长链上的每个点,dfs出其子树中理他最远的点,若两点之间的距离等于该点到直径一个端点的距离,那么显然这个点到端点之间这一段就不能用来统计答案了。
然后我们可以从左往右做一便这个操作,反向再做一遍,中间部分即为直径的并。
代码:
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
vector<int> a[],b[];
int last[],u,v,next[];
long long dis[],mmm[],op;
bool vv[];
void dfs1(int o,long long p,int q)
{
if(p>op){op=p;u=o;}
for(int i=;i<a[o].size();i++)
if((!vv[a[o][i]])&&(a[o][i]!=q))
{
vv[a[o][i]]=true;
dfs1(a[o][i],p+b[o][i],o);
}
}
void dfs2(int o,long long p,int q)
{
last[o]=q;
dis[o]=p;
if(p>op){op=p;v=o;}
for(int i=;i<a[o].size();i++)
if((!vv[a[o][i]])&&(a[o][i]!=q))
{
vv[a[o][i]]=true;
dfs2(a[o][i],p+b[o][i],o);
}
}
int main()
{
int n;
cin>>n;
for(int i=;i<n;i++)
{
int x,y,z;
cin>>x>>y>>z;
a[x].push_back(y);
b[x].push_back(z);
a[y].push_back(x);
b[y].push_back(z);
}
memset(vv,,sizeof(vv));op=;
dfs1(,,);
memset(vv,,sizeof(vv));op=;
dfs2(u,,);
int distance=dis[v];
cout<<dis[v]<<endl;
memset(vv,,sizeof(vv));
for(int i=v;i!=;i=last[i]) vv[i]=true;
for(int i=v;i!=;i=last[i])
{
op=;
dfs1(i,,);
mmm[i]=op;
}
int j=v;
for(int i=last[v];i!=;i=last[i]) next[i]=j,j=i;
int ans=;
int i;
for(i=j;i!=;i=next[i])
if(dis[v]-dis[i]==mmm[i]) break;
for(;i!=;i=last[i])
{
if(dis[i]==mmm[i]) break;
ans++;
}
cout<<ans<<endl;
return ;
}
最新文章
- 那些年我们写过的T-SQL(上篇)
- JS是按值传递还是按引用传递
- MPlayer 增加边看边剪切功能
- 提升WordPress站点速度的八个建议
- Flex 三态复选框
- cocos2d-x jsbinding 在线更新策略设计
- insert into ... on duplicate key update 与 replace 区别
- [BZOJ 2594] [Wc2006]水管局长数据加强版 【LCT】
- 国内常用ntp服务器ip地址
- WPF事件,路由事件
- 关于Winform中的用户代理
- Python中三种基本结构的语句
- JSP的四个作用域
- glusterfs 步骤
- IPFS: BitSwap协议(数据块交换)
- [LeetCode] Knight Probability in Chessboard 棋盘上骑士的可能性
- React文档(十九)不使用ES6
- springmvc功能以及源码实现分析
- Linux中非正常关闭vi编辑器产生swp文件怎么删除
- Java 清理和垃圾回收