CF862 div2 D. A Wide, Wide Graph

╰+攻爆jí腚メ 2024-03-24 14:04 40阅读 0赞

[Problems - Codeforces][]

![d54b2f1d55aa48239a91dc1fcb026829.png][]

思路：

因为要我们输出k为1~n的答案，因此一定要去枚举k

然后对于枚举的每一个k，这个k值实际上指的是“半径”，对于树上一个结点，它与该半径之外的结点可以构成连通块，在半径里面的就不行，因此，对于那些离该结点最远距离的结点的距离都<k的结点来说，这些结点都是孤立的点，它们自己构成了一个连通块，其余的结点都构成一个连通块

因此我们需要去统计这些孤立的结点的个数

怎么去统计？我们可以预处理出所有结点到该结点所在连通块的其余结点的最远距离，如果该最远距离<k，则为孤立点

怎么去预处理？这个就是树的直径的典，两次dfs预处理出所有结点离直径两端点的最大距离就行

有一个结论就是，对于一个普通的结点，它离该连通块最远的距离就是它到直径两端点之一的距离取最大

Code:

#include <bits/stdc++.h>
    using namespace std;
    #define int long long
    using i64 = long long;
    const int mxn=1e6+10;
    const int mxe=1e6+10;
    const int mod=1e9+7;
    struct ty{
        int to,next;
    }edge[mxe<<1];
    
    int n,m,u,v,tot=0;
    int head[mxn],dis[mxn],d[mxn];
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void G_init(){
        tot=0;
        for(int i=0;i<=n;i++){
            head[i]=-1;
            dis[i]=0;
            d[i]=0;
        }
    }
    void dfs(int u,int fa){
        dis[u]=dis[fa]+1;
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dfs(edge[i].to,u);
        }
    }
    void solve(){
        cin>>n;
        G_init();
        for(int i=1;i<=n-1;i++){
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }
        dfs(1,1);
        int mx=-1,pos=0;
        for(int i=1;i<=n;i++){
            if(mx<dis[i]){
                mx=dis[i];
                pos=i;
            }
        }
        dis[pos]=0;
        dfs(pos,pos);
        mx=-1;
        for(int i=1;i<=n;i++){
            d[i]=dis[i];
            if(mx<dis[i]){
                mx=dis[i];
                pos=i;
            }
        }
        dis[pos]=0;
        dfs(pos,pos);
        for(int i=1;i<=n;i++){
            d[i]=max(d[i],dis[i])-1;
        }
        int ans=0,now=1;
        sort(d+1,d+1+n);
        for(int i=1;i<=n;i++){
            while(now<=n&&d[now]<i) ans++,now++;
            cout<<min(ans+1,n)<<" \n"[i==n];
        }
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[Problems - Codeforces]: https://codeforces.com/contest/1805/problems
[d54b2f1d55aa48239a91dc1fcb026829.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/85ca13146aff464aa199db4c25fbc550.png