PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: pols_agyi_pols
Tester: kingmessi
Editorialist: iceknight1093
DIFFICULTY:
Medium
PREREQUISITES:
Heavy-Light Decomposition
PROBLEM:
You’re given a tree on N vertices and a permutation P.
For each k = 1, 2, \ldots, N solve the following problem:
- You’re allowed to delete an edge from the tree and then add a different edge as long as the graph remains a tree.
- Find the minimum number of such moves needed so that \text{dist}(P_i, P_j) is even for every 1 \le i \lt j \le k in the final tree.
Print -1 if it’s not possible.
EXPLANATION:
Let’s solve the problem for a fixed value of k.
We want \text{dist}(P_i, P_j) to be even for each 1 \le i \lt j \le k.
A tree is a bipartite graph with a unique bipartition (upto swapping the parts), so the above condition is equivalent to saying that all the vertices P_1, P_2, \ldots, P_k lie in the same part of the bipartition.
A simpler way to state this is: if we root the tree at some vertex, say 1, all of P_1, P_2, \ldots, P_k must have the same distance parity from vertex 1.
In particular, note that for k = N no solution can exist so the answer is always -1, while for k \lt N a solution always exists since we can turn the tree into a star centered at P_N.
(Technically N = 1 is an edge case here, but the constraints guarantee N \ge 3 so we don’t need to worry about it.)
Now let’s look at minimizing operation usages.
We are allowed to delete and re-add edges freely.
This can be thought of as first deleting several edges from the tree to create a forest; and then adding edges to connect this forest back into a tree, somehow.
Let’s call the vertices P_1, P_2, \ldots, P_k active.
We’ll also call a vertex even if its distance to 1 (in the original tree) is even, and odd otherwise.
Observe that after deleting edges to obtain the forest, within each component of the forest all active vertices must have the same parity, i.e. they must all be even or they must all be odd.
This is because adding new edges won’t change their relative parities.
So, a necessary condition for a set of edges to be deletable is that in every resulting component, the active vertices are either all even or all odd.
This condition is also sufficient, since we’re working with k \lt N, i.e. as long as this holds it’s always possible to connect things back to form a tree satisfying the necessary condition:
- Without loss of generality, every component contains at least one active vertex (otherwise, we could’ve deleted fewer edges.)
- Since k \lt N, there exists at least one component that contains both an active vertex and an inactive vertex.
- Pick this component, root at an inactive vertex that’s adjacent to an active vertex, and then add edges from the root to some active vertex in each other component. The resulting tree satisfies our condition.
The aim is now to pick a minimal set of edges that satisfies the above condition, i.e. after deletion, in each component all active vertices have the same parity.
This is relatively easy to do in \mathcal{O}(N) time using subtree DP: define dp(u, p) to be the answer for the subtree of u, if the active nodes in the component containing u have parity p; transitions are straightforward since for each child you either keep the same parity or delete the edge and switch to the opposite parity, whichever is cheaper.
This gives us a solution to the problem in \mathcal{O}(N^2) time, which is of course too slow.
The aim now is to figure out a way to speed this up.
Suppose we’ve computed the answer for k, and we now want to compute the answer for k+1.
The only difference between these two scenarios is that the vertex P_{k+1} is now active.
In particular, note that this means the only vertices whose DP values can change, are ancestors of P_{k+1} (including P_{k+1} itself.)
Let’s figure out exactly what changes.
For the node u, we have
where c ranges across all children of u.
Of course, if u is active then we can say dp(u, p) = \infty if p is not equal to the parity of the distance of u, to signify that this case is impossible (in practice, \infty can be just any value larger than N.)
Since we want to perform “updates” on paths, a natural structure to look towards is heavy-light decomposition.
Let’s perform heavy-light decomposition. Then, for a vertex u, let, lt(u) denote the set of light children of u, and hv(u) denote the heavy child of u.
Since the only “long” paths in the decomposition consist of several heavy edges in a row, let’s rewrite our DP transition to reflect this, as follows:
For simplicity, define A_{u, p} = \sum_{c \in lt(u)} \min(dp(c, p), dp(c, 1-p) + 1) to be the value contributed by all the light children of u.
This means the transition is
Now, when we update some vertex, observe that the A_{v, p} values change for only \mathcal{O}(\log N) of its ancestors (each time we move up along a light edge, basically.)
So, we can focus on just keeping each heavy path updated appropriately, and just recalculate the answers for the new vertex on each heavy path as and when we move up.
(Note that we also need to take care of the \infty case for already-active vertices at non-matching p, but this can be wrapped into the A_{u, p} values.)
Along each heavy path, what we have is pretty much a (\min, +) convolution, and so at each vertex we can store the 2\times 2 matrix
and it can be verified that the composition of these two matrices (where “multiplication” is + and “addition” is \min) gives exactly the DP transitions we have.
We can thus build a segment tree along each heavy path to allow for quick composition along paths.
Each time we update a vertex, \mathcal{O}(\log N) heavy paths are affected, since only the matrix corresponding to one vertex on a heavy path changes.
This gives us a solution with complexity \mathcal{O}(N\log ^2 N), which is fast enough.
TIME COMPLEXITY:
\mathcal{O}(N \log^2 N) per testcase.
CODE:
Tester's code (C++)
//Har Har Mahadev
#include<bits/stdc++.h>
#include <algorithm>
#include <cassert>
#include <functional>
#include <vector>
#ifdef _MSC_VER
#include <intrin.h>
#endif
#if __cplusplus >= 202002L
#include <bit>
#endif
namespace atcoder {
namespace internal {
#if __cplusplus >= 202002L
using std::bit_ceil;
#else
unsigned int bit_ceil(unsigned int n) {
unsigned int x = 1;
while (x < (unsigned int)(n)) x *= 2;
return x;
}
#endif
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
unsigned long index;
_BitScanForward(&index, n);
return index;
#else
return __builtin_ctz(n);
#endif
}
constexpr int countr_zero_constexpr(unsigned int n) {
int x = 0;
while (!(n & (1 << x))) x++;
return x;
}
} // namespace internal
} // namespace atcoder
namespace atcoder {
#if __cplusplus >= 201703L
template <class S, auto op, auto e> struct segtree {
static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
"op must work as S(S, S)");
static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
"e must work as S()");
#else
template <class S, S (*op)(S, S), S (*e)()> struct segtree {
#endif
public:
segtree() : segtree(0) {}
explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
size = (int)internal::bit_ceil((unsigned int)(_n));
log = internal::countr_zero((unsigned int)size);
d = std::vector<S>(2 * size, e());
for (int i = 0; i < _n; i++) d[size + i] = v[i];
for (int i = size - 1; i >= 1; i--) {
update(i);
}
}
void set(int p, S x) {
assert(0 <= p && p < _n);
p += size;
d[p] = x;
for (int i = 1; i <= log; i++) update(p >> i);
}
S get(int p) const {
assert(0 <= p && p < _n);
return d[p + size];
}
S prod(int l, int r) const {
assert(0 <= l && l <= r && r <= _n);
S sml = e(), smr = e();
l += size;
r += size;
while (l < r) {
if (l & 1) sml = op(sml, d[l++]);
if (r & 1) smr = op(d[--r], smr);
l >>= 1;
r >>= 1;
}
return op(sml, smr);
}
S all_prod() const { return d[1]; }
template <bool (*f)(S)> int max_right(int l) const {
return max_right(l, [](S x) { return f(x); });
}
template <class F> int max_right(int l, F f) const {
assert(0 <= l && l <= _n);
assert(f(e()));
if (l == _n) return _n;
l += size;
S sm = e();
do {
while (l % 2 == 0) l >>= 1;
if (!f(op(sm, d[l]))) {
while (l < size) {
l = (2 * l);
if (f(op(sm, d[l]))) {
sm = op(sm, d[l]);
l++;
}
}
return l - size;
}
sm = op(sm, d[l]);
l++;
} while ((l & -l) != l);
return _n;
}
template <bool (*f)(S)> int min_left(int r) const {
return min_left(r, [](S x) { return f(x); });
}
template <class F> int min_left(int r, F f) const {
assert(0 <= r && r <= _n);
assert(f(e()));
if (r == 0) return 0;
r += size;
S sm = e();
do {
r--;
while (r > 1 && (r % 2)) r >>= 1;
if (!f(op(d[r], sm))) {
while (r < size) {
r = (2 * r + 1);
if (f(op(d[r], sm))) {
sm = op(d[r], sm);
r--;
}
}
return r + 1 - size;
}
sm = op(d[r], sm);
} while ((r & -r) != r);
return 0;
}
private:
int _n, size, log;
std::vector<S> d;
void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};
} // namespace atcoder
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define repin rep(i,0,n)
#define di(a) int a;cin>>a;
#define precise(i) cout<<fixed<<setprecision(i)
#define vi vector<int>
#define si set<int>
#define mii map<int,int>
#define take(a,n) for(int j=0;j<n;j++) cin>>a[j];
#define give(a,n) for(int j=0;j<n;j++) cout<<a[j]<<' ';
#define vpii vector<pair<int,int>>
#define sis string s;
#define sin string s;cin>>s;
#define db double
#define be(x) x.begin(),x.end()
#define pii pair<int,int>
#define pb push_back
#define pob pop_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bpc(x) __builtin_popcountll(x)
#define btz(x) __builtin_ctz(x)
using namespace std;
using namespace atcoder;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<pair<int, int>, null_type,less<pair<int, int> >, rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
const long long INF=1e18;
const long long M=1e9+7;
const long long MM=998244353;
int power( int N, int M){
int power = N, sum = 1;
if(N == 0) sum = 0;
while(M > 0){if((M & 1) == 1){sum *= power;}
power = power * power;M = M >> 1;}
return sum;
}
const int MX = 2e5+5;
template<int SZ> struct HLD {
int N; vi adj[SZ];
int par[SZ], root[SZ], depth[SZ], sz[SZ], ti;
int pos[SZ]; vi rpos;
void ae(int x, int y) { adj[x].pb(y), adj[y].pb(x); }
void dfsSz(int x) {
sz[x] = 1;
for(auto& y : adj[x]) {
par[y] = x; depth[y] = depth[x]+1;
adj[y].erase(find(be(adj[y]),x));
dfsSz(y); sz[x] += sz[y];
if (sz[y] > sz[adj[x][0]]) swap(y,adj[x][0]);
}
}
void dfsHld(int x) {
pos[x] = ti++; rpos.pb(x);
for(auto y : adj[x]) {
root[y] = (y == adj[x][0] ? root[x] : y);
dfsHld(y); }
}
void init(int _N, int R = 0) { N = _N;
par[R] = depth[R] = ti = 0; dfsSz(R);
root[R] = R; dfsHld(R);
}
void clear(){
rep(i,0,N+1){
par[i]=0,root[i]=0,depth[i]=0,sz[i]=0,pos[i]=0;
adj[i].clear();
}
ti=0;rpos.clear();
}
int lca(int x, int y) {
for (; root[x] != root[y]; y = par[root[y]])
if (depth[root[x]] > depth[root[y]]) swap(x,y);
return depth[x] < depth[y] ? x : y;
}
int dist(int x, int y) {
return depth[x]+depth[y]-2*depth[lca(x,y)]; }
vector<pair<int, int>> ascend(int u, int v) const {
vector<pair<int, int>> res;
while (root[u] != root[v]) {
res.emplace_back(pos[u], pos[root[u]]);
u = par[root[u]];
}
if (u != v) res.emplace_back(pos[u], pos[v] + 1);
return res;
}
vector<pair<int, int>> descend(int u, int v) const {
if (u == v) return {};
if (root[u] == root[v]) return {{pos[u] + 1, pos[v]}};
auto res = descend(u, par[root[v]]);
res.emplace_back(pos[root[v]], pos[v]);
return res;
}
};
HLD<MX> hl;
struct S {
array<array<int,2>,2> a;
};
int add(int x, int y) {
if (x == INF || y == INF) return INF;
return x+y;
}
S op(S l, S r) {
S ans;
rep(i,0,2) {
rep(j,0,2) {
ans.a[i][j] = min(
add(l.a[i][0], r.a[0][j]),
add(l.a[i][1], r.a[1][j])
);
}
}
return ans;
}
S e() {
S ans;
ans.a[0][0] = 0;
ans.a[0][1] = INF;
ans.a[1][0] = INF;
ans.a[1][1] = 0;
return ans;
}
void solve()
{
int n;
cin >> n;
rep(i,0,n-1){
int u,v;
cin >> u >> v;
hl.ae(u,v);
}
vi p(n);
take(p,n);
hl.init(n+1, 1);
vi color(n+1), fixed(n+1, 0), chainEnd(n+1, -1);
vector<array<int,2>> light(n+1), dp(n+1);
rep(i,1,n+1) {
color[i] = hl.depth[i] & 1;
light[i] = {0, 0};
dp[i] = {0, 0};
chainEnd[hl.root[i]] = max(chainEnd[hl.root[i]], hl.pos[i]);
}
auto make_matrix = [&](int v) {
int b0 = light[v][0];
int b1 = light[v][1];
if (fixed[v]) {
if (color[v] == 0) b1 = INF;
else b0 = INF;
}
S res;
res.a[0][0] = b0;
res.a[0][1] = add(b0, 1);
res.a[1][0] = add(b1, 1);
res.a[1][1] = b1;
return res;
};
vector<S> init(n);
rep(i,0,n) {
int node = hl.rpos[i];
init[i] = make_matrix(node);
}
segtree<S, op, e> seg(init);
auto contrib = [&](array<int,2> val, int s) {
return min(val[s], add(val[s ^ 1], 1));
};
auto chain_value = [&](int h) {
S cur = seg.prod(hl.pos[h], chainEnd[h] + 1);
array<int,2> val;
val[0] = min(cur.a[0][0], cur.a[0][1]);
val[1] = min(cur.a[1][0], cur.a[1][1]);
return val;
};
auto update = [&](int v) {
seg.set(hl.pos[v], make_matrix(v));
};
auto propagate = [&](int v) {
while (true) {
int h = hl.root[v];
array<int,2> old = dp[h];
array<int,2> now = chain_value(h);
if (old == now) break;
dp[h] = now;
if (h == 1) break;
int par = hl.par[h];
rep(s,0,2) {
light[par][s] += contrib(now, s) - contrib(old, s);
}
update(par);
v = par;
}
};
vector<int> ans(n);
rep(i,0,n) {
int x = p[i];
fixed[x] = 1;
update(x);
propagate(x);
if (i == n - 1) ans[i] = -1;
else ans[i] = min(dp[1][0], dp[1][1]);
}
give(ans,n);
cout << '\n';
hl.clear();
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while(t--) solve();
return 0;
}