Submission #317145

#	Time	Username	Problem	Language	Result	Execution time	Memory
317145		8e7	Balanced Tree (info1cup18_balancedtree)	C++14	0 / 100	18 ms	12288 KiB

balancedtree

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#define ll long long
#define pii pair<int, int>
#define ff first
#define ss second
#define maxn 500005
using namespace std;
const int inf = 8e7;
vector<int> adj[maxn];
int c[maxn];
pii val[maxn];
pii dfs(int n, int par) {
	pii ret = make_pair(inf, inf);
	for (int v:adj[n]) {
		if (v != par) {
			pii res = dfs(v, n);
			ret.ff = min(ret.ff, res.ff + 1);
			ret.ss = min(ret.ss, res.ss + 1);
		}
	}
	val[n] = ret;
	if (c[n]) ret.ss = 0;
	else ret.ff = 0;
	return ret;
}
void dfs2(int n, int par, pii cur) {
	val[n].ff = min(val[n].ff, cur.ff);
	val[n].ss = min(val[n].ss, cur.ss);
	//cout << n << " " << cur.ff << " " << cur.ss << " " << val[n].ff << " " << val[n].ss<< endl;
	for (int v:adj[n]) {
		if (v != par) {
			pii upd = cur;
			for (int u:adj[n]) {
				if (u != par && u != v) {
					upd.ff = min(upd.ff, val[u].ff + 1);
					upd.ss = min(upd.ss, val[u].ss + 1);
					if (c[u]) upd.ss = 1;
					else upd.ff = 1;
				}
			}
			if (c[n]) {
				upd.ss = 0;
			} else {
				upd.ff = 0;
			}
			upd.ff++, upd.ss++;
			dfs2(v, n, upd);
		}
	}
}
int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		if (n > 17) {
			return 0;
		}
		for (int i = 1;i <= n;i++) c[i] = 0, adj[i].clear();
		for (int i = 0;i < n - 1;i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		int c0 = 0, c1 = 0;
		vector<int> pos;
		for (int i = 1;i <= n;i++) {
			cin >> c[i];
			if (c[i] == 1) c1++;
			else if (c[i] == 0) c0++;
			else pos.push_back(i);
		}
		int s = pos.size();
		int ans = inf, ind = 0;
		if (s) {
			for (int i = 0;i < (1<<s);i++) {
				for (int j = 0;j < s;j++) {
					c[pos[j]] = (i & (1<<j)) ? (c1++, 1) : (c0++, 0);
				}
				dfs(1, 0);
				pii temp = make_pair(inf, inf);
				dfs2(1, 0, temp);
				int num = 0;
				for (int i = 1;i <= n;i++) {
					if (c[i]) num = max(num, val[i].ss);
					else num = max(num, val[i].ff);
				}
				if (num < ans) {
					ans = num, ind = i;
				}
			}
			for (int j = 0;j < s;j++) {
				c[pos[j]] = (ind & (1<<j)) ? 1 : 0;
			}
		} else {
			dfs(1, 0);
			pii temp = make_pair(inf, inf);
			dfs2(1, 0, temp);
			int num = 0;
			for (int i = 1;i <= n;i++) {
				if (c[i]) num = max(num, val[i].ss);
				else num = max(num, val[i].ff);
			}
			ans = num;
		}
		if (ans == inf) {
			cout << -1 << endl;
		} else {
			cout << ans << endl;
			for (int i = 1;i <= n;i++) {
				//cout << val[i].ff << " " << val[i].ss << endl;
				cout << c[i] << " ";
			}
			cout << endl;
		}
	}
}
/*
3
3
1 2
2 3
0 0 -1
4
1 2
2 3
2 4
0 1 0 0

1
8
1 2
1 3
3 4
3 5
3 6
5 7
5 8
0 1 0 0 0 0 0 1

1
6
1 2
2 3
2 4
4 5
4 6
1 0 0 -1 1 0
 */

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