【Tree+贪心】CF1336A

淡淡的烟草味﹌ 2024-03-16 11:07 52阅读 0赞

[Problem - 1336A - Codeforces][]

题意：

![508055dba7b149af910f641158ab8790.png][]

思路：

一开始的思路是按深度给他打标记，然后算贡献

一开始猜了个结论：所有深度一样的点的贡献都是一样的，其实不是

![de79267253ed452b8408f0951c936252.png][]

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mxe=2e5+10;
    const int mod=1e9+7;
    
    priority_queue<int> q;
    
    struct ty{
        int to,next;
    }edge[mxe<<2];
    
    int N,K,u,v,tot=0;
    int a[mxn];
    int head[mxn],sz[mxn],dep[mxn];
    
    void G_init(){
        tot=0;
        for(int i=0;i<=N;i++){
            head[i]=-1;
        }
    }
    void add(int u,int v){
        edge[tot].to=v;
        edge[tot].next=head[u];
        head[u]=tot++;
    }
    void dfs1(int u,int fa){
        sz[u]=1;
        dep[u]=dep[fa]+1;
        for(int i=head[u];~i;i=edge[i].next){
            if(edge[i].to==fa) continue;
            dfs1(edge[i].to,u);
            sz[u]+=sz[edge[i].to];
        }
        q.push(dep[u]-1-(sz[u]-1));
    }
    void solve(){
        cin>>N>>K;
        G_init();
        for(int i=1;i<=N-1;i++){
            cin>>u>>v;
            add(u,v);
            add(v,u);
        }
        dfs1(1,0);
        int ans=0;
        for(int i=1;i<=K;i++){
            int u=q.top();
            q.pop();
            ans+=u;
        }
        cout<<ans<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        int __=1;//cin>>__;
        while(__--)solve();return 0;
    }

[Problem - 1336A - Codeforces]: https://codeforces.com/problemset/problem/1336/A
[508055dba7b149af910f641158ab8790.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/7e962b01cbcf41e3b8ed84d6ca489606.png
[de79267253ed452b8408f0951c936252.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/c180f0a5e9b74209baa226a8c2b24c48.png