树的直径

我先开始以为是个图,想想并不知道什么求图的直径的方法,结果是棵树

那么直觉告诉我们是在直径上面,实际上就是直径+min(i->u,i->v),扫一遍就行了

#include<bits/stdc++.h>
using namespace std;
const int N = ;
namespace IO
{
const int Maxlen = N;
char buf[Maxlen], *C = buf;
int Len;
inline void read_in()
{
Len = fread(C, , Maxlen, stdin);
buf[Len] = '\0';
}
inline void fread(int &x)
{
x = ;
int f = ;
while (*C < '' || '' < *C) { if(*C == '-') f = -; ++C; }
while ('' <= *C && *C <= '') x = (x << ) + (x << ) + *C - '', ++C;
x *= f;
}
inline void read(int &x)
{
x = ;
int f = ; char c = getchar();
while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }
while(c >= '' && c <= '') { x = (x << ) + (x << ) + c - ''; c = getchar(); }
x *= f;
}
inline void read(long long &x)
{
x = ;
long long f = ; char c = getchar();
while(c < '' || c > '') { if(c == '-') f = -; c = getchar(); }
while(c >= '' && c <= '') { x = (x << 1ll) + (x << 3ll) + c - ''; c = getchar(); }
x *= f;
}
} using namespace IO;
struct edge {
int to;
long long w;
edge(int to = , long long w = ) : to(to), w(w) {}
};
int n, m, root;
long long ans;
vector<edge> G[N];
long long f[N], g[N], d[N];
void dfs(int u, int last, long long d[])
{
if(d[u] > d[root]) root = u;
for(int i = ; i < G[u].size(); ++i)
{
edge e = G[u][i];
if(e.to == last) continue;
d[e.to] = d[u] + e.w;
dfs(e.to, u, d);
}
}
int main()
{
read(n);
read(m);
for(int i = ; i <= m; ++i)
{
int u, v;
long long w;
read(u);
read(v);
read(w);
G[u].push_back(edge(v, w));
G[v].push_back(edge(u, w));
}
dfs(, , f);
int u = root;
root = ;
dfs(u, , g);
long long dis = g[root];
u = root;
root = ;
dfs(u, , d);
for(int i = ; i <= n; ++i) ans = max(ans, dis + min(d[i], g[i]));
printf("%lld\n", ans);
return ;
}

最新文章

  1. Lamp和Lnmp环境搭建
  2. 产品研发过程中UCD目标的制定与实现
  3. 【HDU 4940】Destroy Transportation system(无源无汇带上下界可行流)
  4. Ajax与DOM实现动态加载
  5. lr各种问题以及解决办法
  6. poj 2509 Peter&#39;s smokes
  7. Linux/Unix shell 监控Oracle告警日志(monitor alter log file)
  8. 5 MySQL索引
  9. ural 1352. Mersenne Primes
  10. TypeScript 中非代码模块的导入
  11. git push 本地项目推送到远程分支
  12. 在 Ali Kubernetes 系统中,我们这样实践混沌工程
  13. Beta阶段复审
  14. 前端基础(http协议相关篇)
  15. C/C++结构体语法总结
  16. ASP.NET Web API编程——构建api帮助文档
  17. 【模板】BM算法(找线性规律万能模板)
  18. linnx常用命令学习
  19. 最小生成树----prim算法的堆优化
  20. BFS【bzoj1667】: [Usaco2006 Oct]Cows on Skates滑旱冰的奶牛

热门文章

  1. Volume 1. String(uva)
  2. Jmeter关联,正则表达式提取器使用1
  3. centOS 7 换ssh端口
  4. 【转】 Java中的IO整理
  5. PatentTips – EMC Virtual File System
  6. Spring Boot - how to configure port
  7. Windows如何安装MSMQ消息队列
  8. SDUTOJ 2476Period
  9. nopcommerce 电商商城 ASP.NET 开源系统
  10. SQL的事务回滚操作带案例分析