Submission #67572248

---

Source Code Expand

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back

using namespace std;

inline int read();
void write(int);
void writeln(int);

int T;
struct D {
    int N, K;
    vector<pii > E;
};

int main() {
	
    T = read();
    vector<D> Qt(T);
    for(int i = 0; i < T; i++) {
        Qt[i].N = read(), Qt[i].K = read();;
        for(int j = 0; j < Qt[i].N - 1; j++) {
            int u = read(), v = read();
            Qt[i].E.pb({u, v});
        }
    }

    for(int idx = 0; idx < T; idx++) {
        int N = Qt[idx].N, K = Qt[idx].K;
        vector<vector<int> > adj(N + 1);
        for(auto &eg : Qt[idx].E) {
            int u = eg.F, v = eg.S;
            adj[u].pb(v), adj[v].pb(u);
        }

        vector<int> ops(N + 1, -1);
        if(K == 0) for(int i = 1; i <= N; i++) ops[i] = 0;
        else {
            vector<bool> inl(N + 1, 0);
            vector<int> dis(N + 1, -1);
            queue<int> q;
            ops[1] = 0;
            if(K > 0) q.push(1);
            while(!q.empty()) {
                int sz = q.size();
                vector<int> nlv;
                for(int i = 0; i < sz; i++) {
                    int u = q.front();
                    q.pop();
                    vector<int> vis;
                    queue<int> Q;
                    dis[u] = 0, vis.pb(u), Q.push(u);
                    while(!Q.empty()) {
                        int v = Q.front();
                        Q.pop();
                        int d = dis[v];
                        if(d == K) {
                            if(ops[v] == -1 && !inl[v]) {
                                ops[v] = ops[u] + 1;
                                inl[v] = true;
                                nlv.pb(v);
                            }
                        } 
						else {
                            for(int w : adj[v]) {
                                if(dis[w] == -1) {
                                    dis[w] = d + 1;
                                    Q.push(w);
                                    vis.pb(w);
                                }
                            }
                        }
                    }
                    for(int vv : vis) dis[vv] = -1;
                }
                for(int v : nlv) q.push(v), inl[v] = 0;
            }
        }
        for(int i = 2; i <= N; i++) write(ops[i]), putchar(' ');
        putchar('\n');
    }

    return 0;
}

inline int read() {
	int res = 0, f = 1;
	char ch = getchar();
	while( !(ch >= '0' && ch <= '9') ) {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		res = (res << 1) + (res << 3) + (ch ^ 48);
		ch = getchar();
	}
	return res * f;
}

void write(int x) {
	if(x < 0) putchar('-'), x = -x;
	static int sta[35];
	int top = 0;
	do {
		sta[top++] = x % 10;
		x /= 10;
	} while(x);
	while(top) putchar(sta[--top] ^ 48);
}

void writeln(int x) {
	write(x);
	putchar('\n');
}

Submission Info

Judge Result