PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: snow_29
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
DFS
PROBLEM:
You’re given a tree, with two markers: one each at vertices 1 and N.
Some vertices of the tree are special; given as a string S where i is special iff S_i = 1.
In one move, you can choose a marker and move it to an adjacent vertex.
Find the minimum number of moves needed to visit every special vertex with at least one marker, and end up in a state where both markers are back at their initial positions.
EXPLANATION:
Let’s first analyze a simpler version of the problem: what if we had only one marker?
To solve this easy version, it’s perhaps easiest to look at the edges of the tree.
Note that since we need to end up back at 1, each edge of the tree must be traversed an even number of times; because if we ever go ‘down’ an edge then we need to go back ‘up’ along it at some point.
Now, for an edge of the tree connecting u and \text{par}_u, if there’s no vertex in the subtree of u that needs to be visited, there’s no point ever traversing this edge.
After discarding such irrelevant edges, all the remaining edges are important in that we’re forced to pass through them at least once (otherwise we’d end up not visiting some vertex that we need to.)
So, the answer is simply twice the number of remaining edges; since as noted earlier every edge must be traversed an even number of times.
Let’s now extend this idea to two markers.
First, note that because both markers move separately (and not simultaneously), there will exist an optimal solution where no vertex is visited by both markers.
That is, every vertex will be either unvisited entirely, or be visited by exactly one marker.
Proof
For convenience, we’ll call the two markers - marker 1 and marker N.
Suppose there’s a vertex visited by both markers - say vertex u.
Marker 1 visits u, then will have some sequence of operations, and then at some point will visit u for the last time and leave forever (since it needs to end up back at 1).
Marker N also does the same.
What we can instead do is just give the entire sequence of marker 1's moves between its visits to u, to marker N instead (when marker N first visits u).
Because the moves are sequential and not simultaneous, this results in the same number of total moves across both markers.Further, we can actually save two moves: marker 1 no longer needs to even touch u, so the first move to u and the last move from u can be deleted entirely and the set of visited nodes will remain the same.
Repeatedly performing this replacement will give us a solution where no vertex is visited by both markers, as desired.
Let’s now root the tree at vertex 1.
Suppose the path from 1 to N is 1 = x_1 \to x_2 \to x_3 \to\ldots\to x_k = N.
Since we know there exists an optimal solution where the markers never overlap in their visited nodes, such a solution must look as follows:
- Choose some index i (1 \lt i \le k).
We can then fix x_i to be the highest ancestor of N that the marker initially on N visits. - Since this marker never goes higher than x_i (and also the marker at 1 will never visit x_i), we can essentially cut the entire subtree rooted at x_i out of the original tree.
- This gives us two smaller trees: the subtree rooted at x_i (which contains one marker), and the original tree minus this subtree (which contains the other marker).
Each of these trees is now an instance of the one-marker problem, which we know how to solve in linear time (as seen at the start: root at the marker, discard useless edges, the answer is then twice the number of remaining edges).
So, for a fixed i, the minimum number of moves can be computed in linear time.
There are \mathcal{O}(N) choices of i, and we’re allowed \mathcal{O}(N^2) time - so we can simply try every choice and take the best among them.
Though it’s not required in this version of the problem, it’s possible to further optimize this solution to run in linear time.
Understanding this optimization is crucial to solving the harder version of the problem, and so is discussed in that editorial instead.
TIME COMPLEXITY:
\mathcal{O}(N) or \mathcal{O}(N^2) per testcase.
CODE:
Editorialist's code (C++)
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector adj(n, vector<int>());
vector par(n, 0);
for (int i = 1; i < n; ++i) {
cin >> par[i];
--par[i];
adj[i].push_back(par[i]);
adj[par[i]].push_back(i);
}
string s; cin >> s;
int ans = 2*n;
auto solve = [&] (const auto &self, int u, int p) -> array<int, 2> {
int res = 0, subct = s[u] == '1';
for (int v : adj[u]) if (v != p) {
auto [ct, sm] = self(self, v, u);
res += ct;
subct += sm;
}
if (p != -1) res += subct > 0;
return {res, subct};
};
int u = n-1;
while (u > 0) {
int p = par[u];
adj[u].erase(ranges::find(adj[u], p));
adj[p].erase(ranges::find(adj[p], u));
int cur = solve(solve, 0, -1)[0] + solve(solve, n-1, -1)[0];
ans = min(ans, 2*cur);
adj[u].push_back(p);
adj[p].push_back(u);
u = par[u];
}
cout << ans << '\n';
}
}