| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 317200 | casperwang | 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 <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
void DFS(int now, int par, int d0, int d1, vector <int> &dp0, vector <int> &dp1, vector <int> &c, vector<vector<int>> &path, vector<vector<int>> &p2) {
if (par) p2[now].pb(par);
dp0[now] = min(dp0[now], d0);
dp1[now] = min(dp1[now], d1);
for (int i : path[now]) {
if (i == par) continue;
deg[i]--;
if (deg[i] <= 1) {
if (c[now])
DFS(i, now, 1, dp1[now]+1, c, path, p2);
else
DFS(i, now, dp0[now]+1, 1, c, path, p2);
}
}
}
dfs(int now, int par, vector<int> &dp0, vector<int> &dp1, vector<vector<int>> &p2) {
for (int i : p2[now]) {
dp0[i] = min(dp0[i], dp0[now]+1);
dp1[i] = min(dp1[i], dp1[now]+1);
dfs(i, now, dp0, dp1, p2);
}
}
signed main() {
ios_base::sync_with_stdio(0), cin.tie(0);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector <vector<int>> path(n+1), p2(n+1);
vector <int> deg(n+1), dp0(n+1), dp1(n+1);
for (int i = 1; i <= n; i++)
dp0[i] = dp1[i] = n+1;
int a, b;
for (int i = 1; i < n; i++) {
cin >> a >> b;
path[a].pb(b);
deg[a]++;
path[b].pb(a);
deg[b]++;
}
vector <bool> tf(n+1);
vector <int> c(n+1);
for (int i = 1; i <= n; i++)
cin >> c[i];
int ans = 1;
for (int i = 1; i <= n; i++)
if (deg[i] == 1) DFS(i, 0, n+1, n+1, dp0, dp1, c, path, p2);
for (int i = 1; i <= n; i++)
for (int j : p2[i]) tf[j] = 1;
for (int i = 1; i <= n; i++)
if (!tf[i]) dfs(i, 0, dp0, dp1, p2);
for (int i = 1; i <= n; i++)
ans = max({ans, dp0[i], dp1[i]});
if (ans > n) cout << -1 << "\n";
else cout << ans << "\n";
}
}