树的直径最简单证明及代码

转载博客

补充说明

之所以上图可以设一个点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;
}