Submission #1143560

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143560		Muhammet	Balanced Tree (info1cup18_balancedtree)	C++20	0 / 100	5 ms	1860 KiB

balancedtree

#include "bits/stdc++.h"

using namespace std;

const int N = 1e5 + 5;

int n, dp[3][N], a[N];

vector <vector <int>> v;

void f(int x, int y){
	for(auto i : v[x]){
		if(i == y) continue;
		f(i, x);
		dp[1][x] = min((!a[i] ? 0 : dp[1][i]) + 1, dp[1][x]);
		dp[2][x] = min((a[i] ? 0 : dp[2][i]) + 1, dp[2][x]);
	}
	return;
}

void f1(int x, int y){
	int z;
	for(auto i : v[x]){
		if(i == y){
			z = i;
			continue;
		}
		f1(i, x);
	}
	dp[1][x] = min((!a[z] ? 0 : dp[1][z]) + 1, dp[1][x]);
	dp[2][x] = min((a[z] ? 0 : dp[2][z]) + 1, dp[2][x]);
}

void solve(){
	cin >> n;
	v.clear();
	v.resize(n+1);
	for(int i = 1; i < n; i++){
		int u1, u2;
		cin >> u1 >> u2;
		v[u1].push_back(u2);
		v[u2].push_back(u1);
	}

	for(int i = 1; i <= n; i++){
		cin >> a[i];
		dp[1][i] = dp[2][i] = 1e9;
	}

	f(1, 0);

	f1(1, 0);

	int ans = 0, cnt0 = 0, cnt1 = 0;
	for(int i = 1; i <= n; i++){
		if(a[i]){
			cnt1++;
			ans = max(ans, dp[2][i]);
		}
		else {
			cnt0++;
			ans = max(ans, dp[1][i]);
		}
	}
	if(cnt1 == 1 or cnt0 == 1){
		cout << -1 << '\n';
		return;
	}
	cout << ans << '\n';
	for(int i = 1; i <= n; i++){
		cout << a[i] << ' ';
	}
	cout << '\n';
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr);

	int T;
	cin >> T;
	while(T--) solve();

	return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 13
• Subtask 3: 0 / 26
• Subtask 4: 0 / 45
• Subtask 5: 0 / 6