CF 1805 D. A Wide, Wide Graph (*1800) 思维 + 树的直径

CF 1805 D. A Wide, Wide Graph (*1800) 思维 + 树的直径

题目链接

题意：

思路：

若当前点到最远的点的距离 \(< k\) , 说明 \(x\) 自己成为一个联通块。

并且我们知道距离任意一点最远的点一定是树直径的一个端点。

反之，则与直径端点在同一个联通块。

所以一个点要么独立成为联通块，要么和直径端点在一个联通块。

\(dfs\) 求出直径两个端点，并且维护每个点到端点的距离即可。

代码：

#include<bits/stdc++.h>

using namespace std;

using i64=long long;

void Showball(){
     int n;
     cin>>n;
     vector<vector<int>> e(n);
     for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        u--;
        v--;
        e[u].push_back(v);
        e[v].push_back(u);
     }

     vector<int> st(n),dis(n);

     function<void(int)> dfs=[&](int u){
        for(auto v:e[u]){
            if(st[v]) continue;
            st[v]=true;
            dis[v]=dis[u]+1;
            dfs(v);
        }
     };

     st[0]=1;
     dfs(0);
     int maxn=0,S,E;
     for(int i=0;i<n;i++){
        if(dis[i]>maxn){
            maxn=dis[i];
            S=i;
        }
        dis[i]=st[i]=0;
     }
     st[S]=1;
     dfs(S);
     auto dis2=dis;
     
     maxn=0;
     for(int i=0;i<n;i++){
        if(dis[i]>maxn){
            maxn=dis[i];
            E=i;
        }
        dis[i]=st[i]=0;
     }
     st[E]=1;
     dfs(E);
     vector<int> ans(n+1);
     for(int i=0;i<n;i++){
        if(i!=E) ans[max(dis[i],dis2[i])+1]++;
     }
     ans[0]=1;
     for(int i=1;i<=n;i++) ans[i]+=ans[i-1];
     for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t=1;
    //cin>>t;

    while(t--){
      Showball();
    }

    return 0;
}