# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1143018 | tkm_algorithms | Balanced Tree (info1cup18_balancedtree) | C++20 | 0 ms | 0 KiB |
/**
* In the name of Allah
* We are nothing and you're everything
* author: najmuddin
**/
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
#define int ll
const char nl = '\n';
const int N = 1e8+5;
//const int inf = 1e18;
const int mod = 1e9+7;
void solve() {
int n; cin >> n;
vector<int> g[n+10];
bool yest = false;
for (int i = 0; i < n-1; ++i) {
int a, b; cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
vector<int> c(n);
for (auto &i: c) {
cin >> i;
if (i == -1)yest = true;
}
for (int j = 1; j <= n; ++j) {
int ok = c[j-1];
int find = -1;
queue<pair<int, pair<int, pair<int, int>>>> q; // dist, where, par, ok
q.push({0, {j, {-1, ok}}});
while (!q.empty()) {
auto p = q.front();
q.pop();
if (p.second.second.second == ok) {
if (p.first != 0) {
find = p.first;
break;
}
}
for (auto i: g[p.second.first]) {
if (i != p.second.second.first) {
q.push({p.first+1, {i, {p.second.first, c[i-1]}}});
}
}
}
if (find == -1)mx[j] = {mod, j};
else mx[j] = {find, j};
}
sort(mx.rbegin(), mx.rend());
if (!yest) {
if (mx.front().first == mod) {
cout << -1 << nl;
return;
}
cout << mx.front().first << nl;
for (auto i: c)cout << i << ' ';
cout << nl;
}
}
int32_t main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}