PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Easy - Medium
PREREQUISITES:
Trees
PROBLEM:
You are given a tree, each vertex has a value in \{-1, 0, 1\}.
The tree is called consistent if there exists a way to assign the labels 1 to N to the vertices such that, for each vertex u:
- u has value -1 iff its label is smaller than all its neighbors’ labels.
- u has value 1 iff its label is larger than all its neighbors’ labels.
- u has value 0 iff neither of the above.
There are also Q updates to the tree, each toggling a value between 1 and -1.
After each update, decide if the tree is consistent or not.
EXPLANATION:
From the easy version, a tree is consistent if and only if:
- Two vertices with the same non-zero value should not be adjacent.
- A leaf cannot contain 0.
- Consider any connected set of vertices that all have value 0.
This component must be adjacent to at least one -1, and also adjacent to at least one 1.
Let’s now understand how to check this along with updates.
Importantly, note that updates do not change the 0-value vertices at all - they can neither be created nor destroyed.
So, the connected components of 0-value vertices will always remain the same.
Thus, we only need to maintain the following information across updates:
- Are there two vertices with value -1 adjacent to each other?
- Are there two vertices with value 1 adjacent to each other?
- Is there a leaf with value 0?
- For each component of 0’s, is it adjacent to both a 0 and a 1?
Let’s go over each one in turn.
First, checking for adjacent vertices with value -1 or 1.
For this, note that we cannot iterate through all the neighbors of a vertex on each update, since that’s linear time per update at worst.
Instead, we can do the following:
- Root the tree at some vertex initially.
- Then, for each vertex, count and store the number of 1’s and -1’s present among its children.
Once this is done, if a vertex u is flipped,
- Knowing whether it creates a conflict with its children can be found by looking at its children counts, in constant time.
- Only the child count of its parent needs to be updated, which also takes constant time.
Thus, this part takes constant time per update.
Checking for a leaf with value 0 is trivial, and updates don’t change it.
So either the input tree already has this (in which case after every update the answer is No), or the input tree doesn’t and updates can’t change it so we ignore the condition henceforth.
Finally, for each component of 0’s, we want to know whether it’s adjacent to both a 1 and a -1.
Once again, after a flip we can’t iterate over all neighbors to check this - that would be too slow.
However, we can use a similar idea as we did earlier, and separate the checks for the children and the parent.
Updating the parent component (if it exists), takes constant time.
As for the children, we can once again store combined information about all of them, to avoid needing to look at each one.
Specifically, store for each vertex:
- The number of children 0-components that would become “bad”, if this vertex was -1.
- The number of children 0-components that would become “bad”, if this vertex was 1.
When flipping a vertex, this information changes for only at most one component (that being the component containing its parent) so it’s handled in constant time too.
Knowing all this information allows us to process an update in constant time overall, so we’re done.
Alternately, it’s possible to build a segment tree over the BFS order of the tree, allowing for logarithmic queries over the children of any given vertex. This is another way of obtaining a fast solution, at the cost of \mathcal{O}(\log N) time (which is fine for the constraints.)
TIME COMPLEXITY:
\mathcal{O}(N + Q) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
struct node{
int x, cnt;
int lz;
};
struct segtree{
// handle range add, find range min, find range min count
node merge(node a, node b){
node c;
c.x = min(a.x, b.x);
c.cnt = (a.x == c.x) * a.cnt + (b.x == c.x) * b.cnt;
c.lz = 0;
return c;
}
vector <node> seg;
void build(int l, int r, int pos, vector <int> &a){
if (l == r){
seg[pos].x = a[l];
seg[pos].cnt = 1;
seg[pos].lz = 0;
return;
}
int mid = (l + r) / 2;
build(l, mid, pos * 2, a);
build(mid + 1, r, pos * 2 + 1, a);
seg[pos] = merge(seg[pos * 2], seg[pos * 2 + 1]);
}
void updlz(int l, int r, int pos){
seg[pos].x += seg[pos].lz;
if (l != r){
seg[pos * 2].lz += seg[pos].lz;
seg[pos * 2 + 1].lz += seg[pos].lz;
}
seg[pos].lz = 0;
}
void upd(int l, int r, int pos, int ql, int qr, int x){
if (seg[pos].lz) updlz(l, r, pos);
if (l >= ql && r <= qr){
seg[pos].lz += x;
updlz(l, r, pos);
} else if (l > qr || r < ql){
} else {
int mid = (l + r) / 2;
upd(l, mid, pos * 2, ql, qr, x);
upd(mid + 1, r, pos * 2 + 1, ql, qr, x);
seg[pos] = merge(seg[pos * 2], seg[pos * 2 + 1]);
}
}
node query(int l, int r, int pos, int ql, int qr){
if (seg[pos].lz) updlz(l, r, pos);
if (l >= ql && r <= qr){
return seg[pos];
} else if (l > qr || r < ql){
node def;
def.x = INF;
def.cnt = 0;
def.lz = 0;
return def;
} else {
int mid = (l + r) / 2;
node v1 = query(l, mid, pos * 2, ql, qr);
node v2 = query(mid + 1, r, pos * 2 + 1, ql, qr);
return merge(v1, v2);
}
}
void build(int n, vector <int> a){
seg.resize(4 * n + 1);
build(1, n, 1, a);
}
};
struct FenwickTree{
int n;
vector <int> f;
vector <int> b;
inline void add(int i, int x){
b[i] += x;
for (int j = i; j <= n; j += j & (-j)){
f[j] += x;
}
}
inline void modify(int i, int x){
add(i, x - b[i]);
}
inline void init(int nn, vector <int> a){
n = nn;
if (a.size() == n){
vector <int> a2;
a2.push_back(0);
for (auto x : a) a2.push_back(x);
a = a2;
}
f.resize(n + 1);
b.resize(n + 1);
for (int i = 0; i <= n; i++) f[i] = 0, b[i] = 0;
for (int i = 1; i <= n; i++){
modify(i, a[i]);
}
}
inline int query(int x){
int ans = 0;
for (int i = x; i; i -= i & (-i)){
ans += f[i];
}
return ans;
}
inline int query(int l, int r){
return query(r) - query(l - 1);
}
};
void Solve()
{
int n, q; cin >> n >> q;
vector <int> a(n + 1);
for (int i = 1; i <= n; i++){
cin >> a[i];
}
a[0] = 2;
vector<vector<int>> adj(n + 1);
int cross = 0;
for (int i = 1; i < n; i++){
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
cross += (a[u] * a[v]) > 0;
}
bool bad_leaf = false;
for (int i = 1; i <= n; i++) if (a[i] == 0 && (int)adj[i].size() == 1){
bad_leaf = true;
}
vector <int> ord = {0};// bfs ordering
// for every root of 0-component, note how many adjacent are 1s and -1s
vector <int> pos(n + 1, 0), neg(n + 1, 0), par(n + 1);
vector<vector<int>> ch(n + 1);
vector <int> idx(n + 1);
{
queue <int> q;
q.push(1);
vector <bool> vis(n + 1, false);
vis[1] = true;
while (!q.empty()){
int u = q.front(); q.pop();
ord.push_back(u);
for (int v : adj[u]) if (!vis[v]){
par[v] = u;
ch[u].push_back(v);
vis[v] = true;
q.push(v);
}
}
}
for (int i = 1; i <= n; i++){
idx[ord[i]] = i;
}
for (int i = 1; i <= n; i++) if (a[i] == 0){
for (int v : adj[i]){
if (a[v] == 1) pos[i]++;
if (a[v] == -1) neg[i]++;
}
}
vector <int> root(n + 1);
iota(root.begin(), root.end(), 0);
auto find = [&](auto self, int x){
if (root[x] == x) return x;
return root[x] = self(self, root[x]);
};
for (int _ = n; _ >= 1; _--){
int i = ord[_];
if (a[i] == 0 && a[par[i]] == 0){
root[i] = par[i];
pos[par[i]] += pos[i];
neg[par[i]] += neg[i];
}
}
int bad_comp = 0;
for (int i = 1; i <= n; i++){
if (a[i] == 0 && a[par[i]] != 0){
bad_comp += pos[i] == 0 || neg[i] == 0;
} else {
pos[i] = neg[i] = 3 * q + 3 * n + 5;
}
}
vector <int> fix_pos(n + 1), fix_neg(n + 1);
for (int i = 1; i <= n; i++){
fix_pos[idx[i]] = pos[i];
fix_neg[idx[i]] = neg[i];
}
segtree seg[2];
seg[0].build(n, fix_neg);
seg[1].build(n, fix_pos);
FenwickTree fen[2];
vector <int> vv(n + 1);
fen[0].init(n, vv);
fen[1].init(n, vv);
for (int i = 1; i <= n; i++){
if (a[i] == -1){
fen[0].add(idx[i], 1);
} else if (a[i] == 1){
fen[1].add(idx[i], 1);
}
}
auto get = [&](int l, int r, int p){
p = (p + 1) / 2;
node res = seg[p].query(1, n, 1, l, r);
if (res.x == 0){
return res.cnt;
} else {
return 0LL;
}
};
auto update = [&](int l, int r, int p, int v){
p = (p + 1) / 2;
seg[p].upd(1, n, 1, l, r, v);
};
auto get2 = [&](int l, int r, int p){
p = (p + 1) / 2;
return fen[p].query(l, r);
};
auto flip = [&](int l, int r, int x, bool che1 = true, bool che2 = true){
if (!(1 <= l && l <= r && r <= n)) return;
if (che1){
bad_comp -= get(l, r, -x);
update(l, r, x, -1);
update(l, r, -x, +1);
bad_comp += get(l, r, +x);
}
// +x in this range are now -ing to cross, -x are adding to cross
if (che2){
cross += get2(l, r, -x) - get2(l, r, x);
}
};
while (q--){
int u; cin >> u;
if (ch[u].size()){
int l = idx[ch[u][0]];
int r = idx[ch[u].back()];
flip(l, r, a[u]);
}
if (a[par[u]] == 0){
int v = par[u];
v = find(find, v);
flip(idx[v], idx[v], a[u], true, false);
} else {
int v = par[u];
flip(idx[v], idx[v], a[u], false, true);
}
fen[(a[u] + 1) / 2].add(idx[u], -1);
a[u] *= -1;
fen[(a[u] + 1) / 2].add(idx[u], 1);
if (bad_comp == 0 && !bad_leaf && cross == 0){
cout << "Yes\n";
} else {
cout << "No\n";
}
}
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}