模拟求root——cf1067B

#include <bits/stdc++.h>
using namespace std;

#define MOD 1000000007
#define ll long long int
#define vi vector<int>
#define vii vector< vector<int> >
#define PI 3.1415926535897932384626433832795
#define INF 9223372036854775807LL
#define endl "n"

int deg[100005];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k;
    cin >> n >> k;
    vii graph(n+1,vi());
    vector<bool> rem(n+1,false);
    for(int i = 0; i < n-1; i++) {
        int a,b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    if(k > 11) {
        cout << "No";
        return 0;
    }
    while(k > 1) {
        for(int i = 1; i <= n; i++) {//扫一遍剩下的图，求度数 
            if(!rem[i]) {
                for(int u : graph[i]) {
                    if(!rem[u]) {
                        deg[i]++;
                    }
                }
            }
        }
        for(int i = 1; i <= n; i++) {//扫一遍剩余结点 
            if(!rem[i]) {
                int leafcn = 0;
                for(int u : graph[i]) {
                    if(!rem[u] && deg[u] == 1) {//找到了新的叶子 
                        leafcn++;
                    }
                }
                if(leafcn < 3 && leafcn != 0) {//u有儿子且小于3 
                    cout << "No";
                    return 0;
                }
            }
        }
        for(int i = 1; i <= n; i++) {//把叶子删了 
            if(!rem[i] && deg[i] == 1) {
                rem[i] = true;
            }
        }
        memset(deg,0,sizeof(deg));
        k--;
    }
    
    int cn = 0;
    int cnb = 0;
    for(int i = 1; i <= n; i++) {//最后还要再求一次 
        if(!rem[i]) {
            cn++;
            for(int u : graph[i]) {
                if(!rem[u]) {
                    deg[i]++;
                }
            }
            if(deg[i] != 1) {
                cnb++;
            }
        }
    }
    if(cn < 4 || cnb != 1) {
        cout << "No";
    } else {
        cout << "Yes";
    }
    return 0;
}