Submission #317209

#	Time	Username	Problem	Language	Result	Execution time	Memory
317209		Seanliu	Balanced Tree (info1cup18_balancedtree)	C++14	0 / 100	971 ms	61336 KiB

balancedtree

#include <iostream>
#include <vector>
using namespace std;

const int maxN = 3e5 + 326;
int T, N, col[maxN], u, v, dep[maxN], md[maxN][2], ans;
vector<int> adj[maxN];

void dfs(int p = 1, int u = 1){
	dep[u] = dep[p] + 1;
	for(int v : adj[u]) if(p != v){
		dfs(u, v);
		if(!md[u][0]){
			md[u][0] = md[v][0];
		} else {
			ans = max(ans, md[u][0] + md[v][0] - 2 * dep[u]); 
			md[u][0] = max(md[u][0], md[v][0]);
		}
		if(!md[u][1]){
			md[u][1] = md[v][1];
		} else {
			ans = max(ans, md[u][1] + md[v][1] - 2 * dep[u]); 
			md[u][1] = max(md[u][1], md[v][1]);
		}
	}
}

void solve(){
	cin >> N;
	ans = 0;
	for(int i = 0; i < N - 1; i++){
		cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	int hasz = 0, haso = 0;
	for(int i = 1; i <= N; i++){
		cin >> col[i];
		(col[i] ? hasz : haso) += 1;
	}
	if(hasz < 2 || haso < 2){
		cout << -1 << endl;
	} else {
		dfs();
		cout << ans << endl;
		for(int i = 1; i <= N; i++) cout << col[i] << " \n"[i == N];
	}
	for(int i = 1; i <= N; i++){
		vector<int>().swap(adj[i]);
		md[i][0] = md[i][1] = 0;
	}
}

int main(){
	cin >> T;
	while(T--){
		solve();
	}
}

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