当前位置: 首页 > news >正文

树的直径

模板

两次 dfs

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5; 
int n, p, dis[N];
vector<int> g[N];inline int read(){int s=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){s=(s<<3)+(s<<1)+(c^48);c=getchar();}return s*f;
}
void dfs(int x, int fa){for(int i=0;i<g[x].size();i++){int t = g[x][i];if(t == fa)continue;dis[t] = dis[x] + 1;dfs(t, x);}
}
int main(){n = read();for(int i=1;i<n;i++){int u = read(), v = read();g[u].push_back(v);g[v].push_back(u);}dfs(1, 0);p=1;for(int i=1;i<=n;i++)if(dis[p] < dis[i])p=i;memset(dis, 0, sizeof dis);dfs(p, 0);p=1;for(int i=1;i<=n;i++)if(dis[p] < dis[i])p=i;cout << dis[p];return 0;
}

http://www.hskmm.com/?act=detail&tid=24121

相关文章:

  • 深入解析:从零起步学习Redis || 第四章:Cache Aside Pattern(旁路缓存模式)以及优化策略
  • 深度解码电子设计可靠性:形式验证(Formal Verification)如何护航 IC 高质量之路
  • 251004
  • gradle Cause: zip END header not found
  • 10 4
  • 叠爱心(love.*)
  • 从单层感知机到多层感知机(MLP)
  • 机电公司管理小工具|基于微信小应用的机电公司管理小程序设计与实现(源码+数据库+文档)
  • 【性质】CF689D Friends and Subsequences
  • Arduino+数码管 = 量电压 | A+B problem | alphabet
  • 详细介绍:【数据库知识】TxSQL 主从数据库同步底层原理深度解析
  • 2025.10.3 NOIP 模拟赛
  • Python 之操作excel
  • 国家生物信息数据下载
  • linux jenkins服务启动异常等,排查是否日志磁盘空间满 du df命令
  • 详细介绍:LeetCode 391 完美矩形
  • [NOI2025] 集合 题解
  • bi数据报表发送周期,周报和月报获取日期时间
  • 技术Leader的1-3-5沟通法则:向上管理的艺术 - 指南
  • cannot resolve method add in T 及 T 泛型类型生成Excel文件,区别是数据Model不同
  • 测试环境elasticSearch数据泄露排查
  • 深入解析:Spring boot中 限制 Mybatis SQL日志的大字段输出
  • 【AI时代速通QT】第九节:揭秘Qt编译全流程-从.pro材料到可执行程序
  • 考试心得5
  • javascript高级 - Ref
  • Solar9月赛wp - 场
  • 实用指南:深度解析Sora2:技术革命与创意产业的未来图景
  • 自动化安全工具的双刃剑:红队演练揭示安全响应盲区
  • Elastic Search 安装部署最全教程(Docker)
  • 详细介绍:图像分割:PyTorch从零开始实现SegFormer语义分割