| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 317215 | Seanliu | Balanced Tree (info1cup18_balancedtree) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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]);
}
ans = max(md[v][col[u]] - dep[u]);
}
}
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;
dep[i] = 0;
}
}
int main(){
cin >> T;
while(T--){
solve();
}
}