樹的直徑最簡單證明及代碼

轉載部落格

補充說明

之是以上圖可以設一個點X，那是因為這是樹的性質，任何兩個點都可以通過某些路徑使其連通

模闆題

思路

首先建一棵樹，然後對樹上的k個點求一個最大直徑D，然後D/2上取整

AC代碼

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
vector<int>tree[maxn];
struct node{
    int val;
    int index;
    node(){
        val=0;
    }
};
int start,top;
bool flag[maxn];
bool vis[maxn];
node ans;
void dfs(int x,int step){
    if(vis[x]){
        return ;
    }
    vis[x]=true;
    if(step > ans.val && flag[x] ){
        ans.val = step;
        ans.index = x;
    }
    int Size = tree[x].size();
    for(int i=0; i<Size; i++){
        dfs(tree[x][i],step+1);
    }
}
int main(){
    int n, k;
    scanf("%d%d", &n, &k);
    memset(flag, false, sizeof(flag));
    for(int i=1; i<=n-1; i++){
        int x,y;
        scanf("%d%d", &x, &y);
        tree[x].push_back(y);
        tree[y].push_back(x);
    }
    for(int i=1; i<=k; i++){
        int temp;
        scanf("%d", &temp);
        start = temp;
        flag[temp] = true;
    }
    dfs(start,0);///找到另外一個點
    memset(vis, false, sizeof(vis));
    top = ans.index;
    dfs(top,0);
    printf("%d\n", ans.val%2==0?ans.val/2:ans.val/2+1);
    return 0;
}