樹的直徑及其性質

參考：​​樹的直徑及其性質與證明​​

①直徑兩端點一定是兩個葉子節點

②距離任意點最遠的點一定是直徑的一個端點，這個基于貪心求直徑方法的正确性可以得出

③如果第一棵樹直徑兩端點為\((u,v)\)，第二棵樹直徑兩端點為\((x,y)\)，用一條邊将兩棵樹連接配接，那麼新樹的直徑一定是\(u,v,x,y\)中的兩個點

④對于一棵樹，如果在一個點的上接一個葉子節點，那麼最多會改變直徑的一個端點

// Created by CAD on 2020/4/9.
#include <bits/stdc++.h>

#define mst(name, value) memset(name,value,sizeof(name))
using namespace std;

const int maxn=5e4+5;
vector<int> g[maxn];
int a[maxn],dx[maxn],dy[maxn];
int dfs(int x,int f,int *d){
    int ans=x;
    for(auto i:g[x]){
        if(i==f) continue;
        d[i]=d[x]+1;
        int now=dfs(i,x,d);
        if(d[now]>d[ans]) ans=now;
    }
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;++i) cin>>a[i];
    for(int i=1;i<=n-1;++i){
        int u,v;cin>>u>>v;
        g[u].push_back(v),g[v].push_back(u);
    }
    int x=dfs(1,0,dx);  //随機找一個點，找到距離它最遠的一個點，即為直徑的一個端點
    mst(dx,0);
    int y=dfs(x,0,dx);  //從x出發，找到距離x最遠的一個點，為直徑的另一個端點，dx表示點到x的距離
    dfs(y,0,dy);    //求得dy
    
    return 0;
}