思路

  两次bfs找出树的直径并处理出端点离树上各叶子节点的距离,在直径上找一点的子树叶子p3,使得dis(p1,p2) + dis(p2,p3) + dis(p1,p3)最大

  易知上式是路径实长的两倍

 #include <bits/stdc++.h>
#define dbg(x) cout << #x << "=" << x << endl
#define eps 1e-8
#define pi acos(-1.0) using namespace std;
typedef long long LL; template<class T>inline void read(T &res)
{
char c;T flag=;
while((c=getchar())<''||c>'')if(c=='-')flag=-;res=c-'';
while((c=getchar())>=''&&c<='')res=res*+c-'';res*=flag;
} namespace _buff {
const size_t BUFF = << ;
char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
char getc() {
if (ib == ie) {
ib = ibuf;
ie = ibuf + fread(ibuf, , BUFF, stdin);
}
return ib == ie ? - : *ib++;
}
} int qread() {
using namespace _buff;
int ret = ;
bool pos = true;
char c = getc();
for (; (c < '' || c > '') && c != '-'; c = getc()) {
assert(~c);
}
if (c == '-') {
pos = false;
c = getc();
}
for (; c >= '' && c <= ''; c = getc()) {
ret = (ret << ) + (ret << ) + (c ^ );
}
return pos ? ret : -ret;
} const int maxn = 2e5 + ; int head[maxn << ], edge[maxn << ], nxt[maxn << ];
int w[maxn << ];
int vis[maxn];
int dis[maxn]; int n, cnt; void BuildGraph(int u, int v, int c) {
cnt++;
edge[cnt] = v;
nxt[cnt] = head[u];
w[cnt] = c;
head[u] = cnt;
} int bfs(int x) {
memset(vis, , sizeof(vis));
memset(dis, , sizeof(dis));
int pos = ;
queue <int> q;
q.push(x);
vis[x] = ;
int u;
while(!q.empty()) {
u = q.front();
//dbg(u);
q.pop();
for (int i = head[u]; i; i = nxt[i]) {
int v = edge[i];
int d = w[i];
if(vis[v])
continue;
else {
dis[v] = dis[u] + d;
vis[u] = ;
if(dis[v] > dis[pos]) {
pos = v;
}
q.push(v);
}
}
}
return pos;
} int d1[maxn], d2[maxn]; int main()
{
read(n);
int a, b;
for ( int i = ; i < n; ++i ) {
read(a);
read(b);
BuildGraph(a, b, );
BuildGraph(b, a, );
}
int p1, p2;
p1 = bfs();
p2 = bfs(p1);
for ( int i = ; i <= n; ++i ) {
d1[i] = dis[i];
}
int p3 = bfs(p2);
for ( int i = ; i <= n; ++i ) {
d2[i] = dis[i];
}
int p4 = ;
for ( int i = ; i <= n; ++i ) {
if(d1[i] + d2[i] > d1[p4] + d2[p4] && i != p1 && i != p2) {
p4 = i;
}
}
int ans = d1[p4]+d2[p4]+d1[p2];
//dbg(ans);
printf("%d\n",ans / );
printf("%d %d %d\n",p1,p2,p4);
return ;
}

最新文章

  1. CSS实现弹出导航菜单
  2. Jenkins入门系列之——03PDF文档下载
  3. T-SQL 小数点转换百分数
  4. FSMC stm32
  5. mysql 存储过程 事务; mysql的事务中包含一个存储过程
  6. Demo Swig
  7. java_设计模式_装饰者模式_Decorator Pattern(2016-07-28)
  8. 输出宽字符数组 C++
  9. git SSh key多个key对应多个项目
  10. querySelector $() getElementBy区别
  11. WebAPI的压缩
  12. vc++项目 : error PRJ0002 : 错误的结果 1 (从“C:\Program Files\Microsoft SDKs\Windows\v6.0A\bin\rc.exe”返回)。
  13. (转) Unicode(UTF-8, UTF-16)令人混淆的概念
  14. c语言基础学习08_关于内存管理的复习
  15. Fragment概述
  16. NOIP2011Mayan游戏(模拟)
  17. mac java jdk 安装删除
  18. 一些常见的第三方UI库
  19. 使用ntp从时间同步服务器更新centos系统时间的方法
  20. 6-Collision-hdu5114(小球碰撞)

热门文章

  1. 磁盘文件系统管理与LVM逻辑卷
  2. 关于ThinkPHP在Nginx服务器下因PATH_INFO出错的解决方法
  3. 几个点认识Nginx服务器
  4. javascript Date对象 js全部的 时间属性 和 方法
  5. debian 和ubuntu 安装ifconfig 命令
  6. 交换机 路由器 防火墙asa 安全访问、配置 方式
  7. gRPC in ASP.NET Core 3.x - gRPC 简介
  8. 大数相乘----C语言
  9. python2 + Django 中文传到模板页面变Unicode乱码问题
  10. Go语言基础之结构体(面向对象编程上)