Submission #317066

#TimeUsernameProblemLanguageResultExecution timeMemory
317066Kevin_Zhang_TWBalanced Tree (info1cup18_balancedtree)C++17
0 / 100
374 ms30200 KiB
#include<bits/stdc++.h> #define pb emplace_back #define AI(i) begin(i), end(i) using namespace std; using ll = long long; #ifdef KEV #define DE(args...) kout("[ " + string(#args) + " ] : ", args) void kout() { cerr << endl; } template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); } void debug(auto L, auto R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; } #else #define debug(...) 0 #define DE(...) 0 #endif const int MAX_N = 500010, inf = 1e9; int n, c[MAX_N]; vector<int> edge[MAX_N]; void clear() { for (int i = 1; edge[i].size() ; ++i) edge[i].clear(); } int dis[MAX_N], sz[MAX_N]; bool ban[MAX_N]; int dfs_sz(int x, int lst = -1) { sz[x] = 1; for (int u : edge[x]) if (u != lst && !ban[u]) sz[x] += dfs_sz(u, x); return sz[x]; } int dfs_cen(int x, int allsz, int lst = -1) { for (int u : edge[x]) if (u != lst && !ban[u]) if (sz[u] * 2 > allsz) return dfs_cen(u, allsz, x); return x; } void chmin(int &v, int val) { v = min(v, val); } int min_dep[2]; void dfs_update(int x, int lst = -1) { static int d; if (ban[x]) return; ++d; chmin(dis[x], min_dep[c[x]] + d); chmin(min_dep[c[x]], d); for (int u : edge[x]) if (u != lst) dfs_update(u, x); --d; } void dfs_solve(int side) { if (ban[side]) return; int cen = dfs_cen(side, dfs_sz(side)); min_dep[0] = min_dep[1] = inf; min_dep[ c[cen] ] = 0; for (int u : edge[cen]) dfs_update(u); min_dep[0] = min_dep[1] = inf; reverse(AI(edge[cen])); for (int u : edge[cen]) dfs_update(u); chmin(dis[cen], min_dep[c[cen]]); ban[cen] = true; for (int u : edge[cen]) dfs_solve(u); } int cal() { for (int i = 1;i <= n;++i) { dis[i] = inf; ban[i] = false; } dfs_solve(1); return *max_element(dis+1, dis+n+1); } void solve() { cin >> n; clear(); for (int a, b, i = 1;i < n;++i) { cin >> a >> b; edge[a].pb(b); edge[b].pb(a); } for (int i = 1;i <= n;++i) cin >> c[i]; int cn = count(c+1, c+n+1, -1), c0 = count(c+1, c+n+1, 0), c1 = count(c+1, c+n+1, 1); if (min(c0, c1) == 1 && cn == 0) return cout << -1 << '\n', void(); if (cn == 0) { cout << cal() << '\n'; for (int i = 1;i <= n;++i) cout << c[i] << " \n"[i==n]; } else exit(1); } int32_t main() { ios_base::sync_with_stdio(0), cin.tie(0); int T; cin >> T; while (T--) solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...