• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

Codeforces Round #748 (Div. 3) E. Gardener and Tree

开发技术 开发技术 4小时前 2次浏览

简单的拓扑排序应用。
https://codeforces.com/contest/1593/problem/E

题意

给一颗树,每次删除当前树所有的叶子结点,问删除 (k) 轮后还剩多少点

Tutorial

由于一棵树的深度最高是 (O(n)) 删除叶子结点的过程又显然是个拓扑排序里去掉入度为 (0) 节点的操作,因此这题可以直接暴力而我居然想搞直径

点击查看代码
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <vector>
typedef long long ll;
#define endl 'n'
#define P pair<int, int>
#define eps 1e-8
#define IOS                  
    ios::sync_with_stdio(0); 
    cin.tie(0);              
    cout.tie(0);
using namespace std;

const int N = 4e5 + 5;
const int mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
vector<int> mp[N];
int vis[N], deg[N],n,m,k;
int main() {
    IOS
    int T;
    cin>>T;
    while(T--){
        cin >> n>>k;
        for(int i=0,u,v;i<n-1;i++){
            cin>>u>>v;
            mp[u].push_back(v);
            mp[v].push_back(u);
            deg[u]++;
            deg[v]++;
        }

        int cnt = n;
        vector<int> now;
        vector<int> nxt;
        for(int i=1;i<=n;i++){
            if(deg[i] <= 1){
                now.push_back(i);
                vis[i] = 1;
            }
        }
        cnt -= now.size();
        k--;
        while(k-- && now.size()){    
            
            for(auto u:now){
                for(auto v:mp[u]){
                    if(!vis[v]) deg[v]--;
                    
                    if(deg[v] <= 1 && !vis[v]){
                        nxt.push_back(v);
                        vis[v] = 1;
                    }

                }
            }
            cnt -= nxt.size();
            now = nxt;
            nxt.clear();
        }
        cout << max(0,cnt) << endl;

        for (int i = 1; i <= n; i++) mp[i].clear(), deg[i] = 0,vis[i] = 0;
    }
}

程序员灯塔
转载请注明原文链接:Codeforces Round #748 (Div. 3) E. Gardener and Tree
喜欢 (0)