CodeForces - 1336A Linova and Kingdom

CodeForces - 1336A

就差一点点，很可惜，少发现个很显而易见的结论

就是一个点的价值，实际上就是（这个点的深度 - 之后的点的数目） 就是 \(depth_i - size_i\) 然后只要用dfs维护就好了

然后把一个点的价值用STL优先队列放在一起，贪心完成。但是可能也算不上什么贪心，因为是很朴素的东西

突然想到以前看题解更多的是想看这种\(depth\)和\(size\)是怎么维护的，但是怎么都找不到，真的自己写题解还是感觉，不好写这种东西，有时间或许可以尝试写下题解，也只是分析代码了

但是现在还是进步很大的，只要有了思路怎么写都行

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
struct CodeForces{
    int to,nxt;
}edge[400005];
int ecnt=0;
int n,k;
int head[200005]={0};
int vis[200005]={0};
int siz[200005]={0};
int dep[200005]={0};
priority_queue<int> q;
void build(int from,int to){
    edge[++ecnt].to=to;
    edge[ecnt].nxt=head[from];
    head[from]=ecnt;
}
void init(){
    for(int i=1;i<=200000;++i){
        head[i]=-1;
    }
}
void dfs(int x,int now){
    siz[x]++;
    for(int i=head[x];~i;i=edge[i].nxt){
        int to=edge[i].to;
        if(vis[to]==1) continue;
        vis[to]=1;
        dep[to]=now+1;
        dfs(to,now+1);
        siz[x]+=siz[to];
    }
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);    
    init();
    cin>>n>>k;
    for(int i=1;i<n;++i){
        int to,from;
        cin>>to>>from;
        build(from,to);
        build(to,from);
    }
    vis[1]=1;
    dep[1]=1;
    dfs(1,1);
    for(int i=1;i<=n;++i){
        q.push(dep[i]-siz[i]);
    }
    int ans=0;
    for(int i=1;i<=k;++i){
        int tt=q.top();
        q.pop();
        ans+=tt;
    }
    cout<<ans<<endl;
    return 0;
}