HihoCoder-1050 【裸树的直径】
解释 :
求树的最长路(树的直径)
首先假设树的最长路的两个叶子节点为v1,v2,那么现有结论,从任意一点u出发走到的最远的点一定是(v1,v2)中的一点,然后再从v1或者v2出发走到的最远点一定是v2或者v1。所以经过两次搜索就能找到最长路径。
AC代码:
dfs 找节点
#include#include #include #define CLR(x) memset(x,0,sizeof(x)) using namespace std; const int maxn=1e5+5; int dep[maxn]; int max_len,root,n; int vis[maxn]; vector ve[maxn]; int dfs(int x,int len) { vis[x]=1; if(len >max_len) max_len=len,root=x; for(int i=0;i