提出 #52221621

---

ソースコード 拡げる

#include <bits/stdc++.h>
#define pii pair<int, int>
#define piii tuple<int, int, int>
#define pll pair<long long, long long>
#define L(n) (n << 1)
#define R(n) (n << 1 | 1)
#define print_vector(n, delimiter) for(auto a0 : n) cout << a0 << delimiter; cout << endl;
#define vector_sort(n) sort(n.begin(), n.end())
#define print_array(n, l, r, delimiter) for(int a0 = l; a0 <= r; a0++) cout << n[a0] << delimiter; cout << '\n';
#define REP(i, l, r) for (int i = l; i <= r; i++) 
#define VREP(i, l, r) for (int i = l; i >= r; i--) 
#define MIN(a, b) (a < b ? a : b)
#define MAX(a, b) (a > b ? a : b)
#define ABS(a) ((a) > 0 ? (a) : -(a))
#define LOG2(n) (31 - __builtin_clz(n))
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <class T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;

template<class T>
istream & operator >> (istream &in, pair<T, T> &p) {
	in >> p.first >> p.second;
	return in;
}

template<class T>
ostream & operator <<(ostream &out, pair<T, T> &p) {
	out << p.first << ' ' << p.second;
	return out;
}

template<class Tuple, std::size_t N>
struct TuplePrinter {
	static void print(ostream &out, const Tuple& t) {
		TuplePrinter<Tuple, N-1>::print(out, t);
		out << ' ' << get<N-1>(t);
	}
};

template<class Tuple>
struct TuplePrinter<Tuple, 1> {
	static void print(ostream &out, const Tuple& t) {
		out << get<0>(t);
	}
};

template<class... Args>
ostream & operator <<(ostream &out, const tuple<Args...> &p) {
	TuplePrinter<decltype(p), sizeof...(Args)>::print(out, p);
	return out;
}

const int MAX_N = 2e5;

int N;
long long K;

vector<int> adj[MAX_N + 5];
vector<int> adjTree[MAX_N + 5];

long long mxAns = 0, mnAns = 0;
long long subSz[MAX_N + 5];
long long depth[MAX_N + 5];

void DFS0(int u, int p) {
	subSz[u] = 1;
	depth[u] = depth[p] + 1;
	for (int v : adj[u]) {
		if (v == p) continue;
		adjTree[u].emplace_back(v);
		DFS0(v, u);
		subSz[u] += subSz[v];
	}
	mnAns = max(mnAns, subSz[u]);
	mxAns += subSz[u];
}

bool used[MAX_N + 5];
int ans[MAX_N + 5];
int p_ans;

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin >> N >> K;
	for (int i = 1; i < N; i++) {
		int u, v;
		cin >> u >> v;
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	DFS0(1, 0);
	if (K < mnAns || K > mxAns) {
		cout << "No\n";
	} else {
		vector<int> sortedSubSz(N);
		iota(sortedSubSz.begin(), sortedSubSz.end(), 1);
		sort(sortedSubSz.begin(), sortedSubSz.end(), [&](const int lhs, const int rhs) {
			return subSz[lhs] > subSz[rhs];
		});
		
		long long k = K;
		vector<int> notUseds;
		vector<int> useds;
		for (int u : sortedSubSz) {
			if (subSz[u] <= k) {
				k -= subSz[u];
				// used[u] = true;
				useds.emplace_back(u);
			} else {
				notUseds.emplace_back(u);
			}
		}
		// print_vector(useds, ' ');
		
		sort(notUseds.begin(), notUseds.end(), [&](const int lhs, const int rhs) {
			return depth[lhs] > depth[rhs];
		});
		for (int u : notUseds) {
			ans[u] = ++p_ans;
		}

		sort(useds.begin(), useds.end(), [&](const int lhs, const int rhs) {
			return depth[lhs] < depth[rhs];
		});
		for (int u : useds) {
			ans[u] = ++p_ans;
		}
		cout << "Yes\n";
		print_array(ans, 1, N, ' ');
	}
}

提出情報

ジャッジ結果