Search for a command to run...
Progressive hints first, then the full explanation and implementation when you're ready to cash out.
Review status
AI-generated and still unreviewed. Double-check the details before internalizing them.
Hints
Open only as much as you need to keep the solve alive.
Forget the queries for a second. For a fixed monster set, one root-starting path can cover monsters only if they all lie on one ancestor-descendant chain. So the answer is the minimum number of chains needed to cover the marked vertices in the rooted tree.
That minimum is exactly the number of marked vertices that have no marked vertex below them. In other words: count monster vertices such that the subtree of contains exactly one monster, namely itself. These are the lowest monsters. Everything above them gets covered for free by the path to them.
After Euler tour flattening, subtree flips become interval bit flips on an array. The hard part is not maintaining the number of ones. The answer is
For a marked vertex , look at the next marked Euler position after . Vertex contributes iff that next marked position does not exist or is greater than .
Maintain marked Euler positions under interval xor flips with a lazy segment tree. Each node stores first, last, and ans. When merging left and right, only the last marked position of the left child can change contribution, because its next marked position may become the first marked position of the right child. Store two summaries per node: current bits and inverted bits. A full flip just swaps them.
For a fixed set of monsters, the answer has a much simpler meaning than the statement makes it look.
A root-starting path is just a chain from vertex down to some vertex. If a monster is an ancestor of another monster, the path to the lower monster already covers the upper one. So only the monsters that are not ancestors of any other monster force separate paths.
Call these terminal monsters: marked vertices with no marked vertex strictly inside their subtree. The answer is exactly the number of terminal monsters.
Why?
So the dynamic problem is:
Maintain the number of marked vertices such that there is no marked vertex strictly in 's subtree, while queries flip all marks in a subtree.
Euler Tour View
Run DFS from the root and assign each vertex an Euler position . The subtree of becomes the contiguous interval
Let who[pos] be the vertex at Euler position pos.
For a marked vertex , the only thing we need is the next marked Euler position after .
Let that position be . Then:
Why does this work? Because every vertex in the subtree of occupies an Euler position from to . So has a marked descendant exactly when the next marked Euler position after is still inside that interval.
Thus the answer is a sum over adjacent marked positions in Euler order. If two consecutive marked positions are , then the vertex at contributes iff
The last marked position always contributes.
Doing this with a set is a trap: flipping a subtree can insert/delete tons of positions. So we need a segment tree that knows how to merge this adjacent-position information.
Segment Tree Summary
For each segment, store:
first: first marked position in the segment, or -1 if empty;last: last marked position in the segment, or -1 if empty;ans: number of terminal contributions using only marked positions inside this segment.The merge is the whole trick.
Suppose we merge left summary and right summary .
All contributions inside and stay valid except possibly one: the last marked position of .
Inside alone, that last marked position was treated like it had no next marked position, so it contributed. But after merging, its next marked position might be the first marked position of .
So if both sides are non-empty, subtract the old contribution of L.last, then add it back only if R.first is outside its subtree:
Everything else keeps the same next marked position as before. Tiny boundary fix, very clean.
For a leaf:
1, summary is {pos, pos, 1};0, summary is empty { -1, -1, 0 }.Handling Flips
A subtree query flips every bit in an interval. A normal segment tree summary for ones is not enough, because after flipping a whole covered node, ones become zeros and zeros become ones.
So store two summaries at every segment tree node:
s[0]: summary for the current bits;s[1]: summary if every bit in this segment were inverted.For an internal node:
When a query fully covers a segment, applying xor flip just swaps s[0] and s[1], and toggles a lazy flag. That is the whole lazy propagation. No heroic nonsense.
After every update, the answer is tree[1].s[0].ans.
Correctness Proof
First, for any fixed monster set, the minimum number of paths equals the number of terminal monsters.
Every terminal monster needs a separate path. If one root-starting path covered two terminal monsters, then those two vertices would lie on one root-to-node chain, so one would be an ancestor of the other. The ancestor would then have a marked descendant, contradicting terminality.
Conversely, take one root-to-vertex path for every terminal monster. Any marked vertex that is not terminal has a marked descendant. Following marked descendants downward eventually reaches a terminal monster, and the path to that terminal monster includes the original vertex. Therefore these paths cover all monsters. So the minimum is exactly the number of terminal monsters.
Second, a marked vertex is terminal iff the next marked Euler position after is absent or greater than .
The subtree of is exactly the Euler interval . A marked strict descendant of exists iff there is some marked Euler position in . That exists iff the next marked position after lies at most . Negating gives the condition.
Third, the segment summary merge is correct.
When concatenating two Euler intervals, every marked position except the last marked position of the left interval has the same next marked position as it had inside its own interval. Every marked position in the right interval also keeps the same next marked position as before. Only the last marked position of the left interval may change: its next marked position becomes the first marked position of the right interval, if that exists. The merge removes its old contribution and recomputes it using the real next marked position. Therefore merged ans is exactly the number of terminal contributions inside the combined interval.
Fourth, lazy flipping is correct.
Each node stores summaries for both possible parities of inversion on its whole segment. Applying a full-segment flip swaps those two summaries and toggles the lazy flag, exactly matching the new bit values. Pushdown propagates the same operation to children, so all partial updates preserve the invariant.
By these facts, after each subtree flip, the root segment summary counts exactly the terminal monsters, which equals the minimum number of root-starting paths.
Complexity
DFS and segment tree build are . Each query is one interval flip, so it costs . Across a test case:
time and memory.
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Summary {
int first = -1;
int last = -1;
int ans = 0;
};
struct SegNode {
Summary s[2];
bool lazy = false;
};
struct Solver {
int n;
vector<int> tin, tout, who, bit;
vector<SegNode> seg;
Summary emptySummary() {
return Summary{-1, -1, 0};
}
Summary oneSummary(int pos) {
return Summary{pos, pos, 1};
}
Summary mergeSummary(const Summary &L, const Summary &R) {
if (L.first == -1) return R;
if (R.first == -1) return L;
Summary res;
res.first = L.first;
res.last = R.last;
res.ans = L.ans + R.ans - 1;
int u = who[L.last];
if (R.first > tout[u]) res.ans++;
return res;
}
void pull(int p) {
seg[p].s[0] = mergeSummary(seg[p << 1].s[0], seg[p << 1 | 1].s[0]);
seg[p].s[1] = mergeSummary(seg[p << 1].s[1], seg[p << 1 | 1].s[1]);
}
void applyFlip(int p) {
swap(seg[p].s[0], seg[p].s[1]);
seg[p].lazy = !seg[p].lazy;
}
void push(int p) {
if (!seg[p].lazy) return;
applyFlip(p << 1);
applyFlip(p << 1 | 1);
seg[p].lazy = false;
}
void build(int p, int l, int r) {
seg[p].lazy = false;
if (l == r) {
if (bit[l]) {
seg[p].s[0] = oneSummary(l);
seg[p].s[1] = emptySummary();
} else {
seg[p].s[0] = emptySummary();
seg[p].s[1] = oneSummary(l);
}
return;
}
int m = (l + r) >> 1;
build(p << 1, l, m);
build(p << 1 | 1, m + 1, r);
pull(p);
}
void update(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
applyFlip(p);
return;
}
push(p);
int m = (l + r) >> 1;
if (ql <= m) update(p << 1, l, m, ql, qr);
if (qr > m) update(p << 1 | 1, m + 1, r, ql, qr);
pull(p);
}
void run() {
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
tin.assign(n + 1, 0);
tout.assign(n + 1, 0);
who.assign(n + 1, 0);
vector<int> parent(n + 1, 0), it(n + 1, 0), st;
st.push_back(1);
int timer = 0;
while (!st.empty()) {
int u = st.back();
if (it[u] == 0) {
tin[u] = ++timer;
who[timer] = u;
}
if (it[u] == (int)g[u].size()) {
tout[u] = timer;
st.pop_back();
continue;
}
int v = g[u][it[u]++];
if (v == parent[u]) continue;
parent[v] = u;
st.push_back(v);
}
bit.assign(n + 1, 0);
for (int u = 1; u <= n; u++) bit[tin[u]] = a[u];
seg.assign(4 * n + 5, SegNode());
build(1, 1, n);
int q;
cin >> q;
cout << seg[1].s[0].ans << '\n';
while (q--) {
int v;
cin >> v;
update(1, 1, n, tin[v], tout[v]);
cout << seg[1].s[0].ans << '\n';
}
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
Solver solver;
solver.run();
}
return 0;
}#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void setIO() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
}
struct Summary {
int first = -1;
int last = -1;
int ans = 0;
};
struct SegNode {
Summary s[2];
bool lazy = false;
};
struct Solver {
int n;
vector<int> tin, tout, who, bit;
vector<SegNode> seg;
Summary emptySummary() {
return Summary{-1, -1, 0};
}
Summary oneSummary(int pos) {
return Summary{pos, pos, 1};
}
Summary mergeSummary(const Summary &L, const Summary &R) {
if (L.first == -1) return R;
if (R.first == -1) return L;
Summary res;
res.first = L.first;
res.last = R.last;
res.ans = L.ans + R.ans - 1;
int u = who[L.last];
if (R.first > tout[u]) res.ans++;
return res;
}
void pull(int p) {
seg[p].s[0] = mergeSummary(seg[p << 1].s[0], seg[p << 1 | 1].s[0]);
seg[p].s[1] = mergeSummary(seg[p << 1].s[1], seg[p << 1 | 1].s[1]);
}
void applyFlip(int p) {
swap(seg[p].s[0], seg[p].s[1]);
seg[p].lazy = !seg[p].lazy;
}
void push(int p) {
if (!seg[p].lazy) return;
applyFlip(p << 1);
applyFlip(p << 1 | 1);
seg[p].lazy = false;
}
void build(int p, int l, int r) {
seg[p].lazy = false;
if (l == r) {
if (bit[l]) {
seg[p].s[0] = oneSummary(l);
seg[p].s[1] = emptySummary();
} else {
seg[p].s[0] = emptySummary();
seg[p].s[1] = oneSummary(l);
}
return;
}
int m = (l + r) >> 1;
build(p << 1, l, m);
build(p << 1 | 1, m + 1, r);
pull(p);
}
void update(int p, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
applyFlip(p);
return;
}
push(p);
int m = (l + r) >> 1;
if (ql <= m) update(p << 1, l, m, ql, qr);
if (qr > m) update(p << 1 | 1, m + 1, r, ql, qr);
pull(p);
}
void run() {
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
vector<vector<int>> g(n + 1);
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
tin.assign(n + 1, 0);
tout.assign(n + 1, 0);
who.assign(n + 1, 0);
vector<int> parent(n + 1, 0), it(n + 1, 0), st;
st.push_back(1);
int timer = 0;
while (!st.empty()) {
int u = st.back();
if (it[u] == 0) {
tin[u] = ++timer;
who[timer] = u;
}
if (it[u] == (int)g[u].size()) {
tout[u] = timer;
st.pop_back();
continue;
}
int v = g[u][it[u]++];
if (v == parent[u]) continue;
parent[v] = u;
st.push_back(v);
}
bit.assign(n + 1, 0);
for (int u = 1; u <= n; u++) bit[tin[u]] = a[u];
seg.assign(4 * n + 5, SegNode());
build(1, 1, n);
int q;
cin >> q;
cout << seg[1].s[0].ans << '\n';
while (q--) {
int v;
cin >> v;
update(1, 1, n, tin[v], tout[v]);
cout << seg[1].s[0].ans << '\n';
}
}
};
int main() {
setIO();
int T;
cin >> T;
while (T--) {
Solver solver;
solver.run();
}
return 0;
}