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:
Trees
PROBLEM:
You’re given a tree with N vertices.
Alice and Bob take turns marking a previously-unmarked vertex of the tree.
In the end, Alice’s score equals the number of vertices x such that:
- x is marked by Bob, and
- There exist vertices u, v marked by Alice such that x lies on the u\to v path.
Alice wants to maximize her score, Bob wants to minimize it. Find Alice’s final score under optimal play.
EXPLANATION:
Let H = \left\lfloor \frac{N}{2} \right\rfloor.
Because Bob goes second, he will always mark exactly H vertices of the tree in total.
Thus, Alice’s score will equal H - s, where s is the number of vertices Bob manages to “save” from being between two of Alice’s vertices.
Now, note that the leaves of the tree are quite important here: it’s generally optimal for Alice to try and claim vertices that are leaves/near leaves (since paths between leaves will deny a large number of vertices for Bob), while similarly Bob will try to claim leaves too since Alice can’t sandwich them with future moves.
In particular, we have the following.
Call a vertex v heavy if \text{deg}(v) \ge 3.
Then, the main claim is that Alice can ensure that Bob cannot save any heavy vertices.
Proof
If there are no heavy vertices, the claim is obviously true.
If there’s only one heavy vertex, the claim is easy to prove: the tree must look like a star with extended rays, and it’s optimal for Alice’s initial moves to be in different rays (which will naturally ensure Bob can’t save the center.)
So, we assume the tree has at least two heavy vertices.
Let G be the minimal connected subgraph of the tree containing all heavy vertices.
Note that G is itself a tree.
The leaves of G will all be heavy vertices themselves; and there will be at least two such leaves.
Further, each leaf of G will be connected to at least two vertices that don’t belong to G; since they’re heavy but have only one neighbor within G.For each leaf of G, define its out-neighborhood to be the set of its neighbors that don’t belong to G.
We’ll show that Alice can always choose at least one vertex from each out-neighborhood.This is, in fact, trivial to show.
On Alice’s first move, she can choose an arbitrary vertex from some out-neighborhood.
After that,
- If Bob chooses a vertex from an out-neighborhood that Alice hasn’t touched before, Alice on her next move can pick a vertex from the same out-neighborhood.
- Otherwise, Alice can choose an arbitrary vertex from a previously untouched out-neighborhood (if it exists.)
Once this is done, clearly any heavy vertex will lie between two different out-neighborhoods; and since Alice has at least one marked in each one, Bob can’t save the heavy vertex no matter what.
Note that this implies something stronger: if a vertex is on the path between some two heavy vertices, then it can’t be saved either!
This happens automatically: the two heavy endpoints aren’t saved so they’re either chosen by Alice or between two Alice-chosen vertices; and so the middle node will also always end up between two Alice-chosen vertices.
Let’s assume that Alice decides to adopt a strategy that prevents Bob from saving any heavy vertices (or rather, anything within the minimal subtree containing all heavy vertices.)
With this in mind, the only vertices that Bob can possibly save are those “outside” all the heavy vertices.
Let’s try to figure out what Bob’s best possible play is under this assumption.
For any leaf vertex l, let’s define the branch of l to be the set of vertices from l to the nearest heavy vertex to l (excluding said heavy vertex.)
Note that if the tree has no heavy vertices, it is a line. In this case, Bob can only save one vertex since it’s optimal for to Alice choose one endpoint first and Bob can save the other one. This special case aside, we proceed assuming that the tree has at least one heavy vertex, so branches exist.
Bob can only save some of the vertices that are on branches.
Suppose there are k branches, and let the lengths of the branches be x_1, x_2, \ldots, x_k.
Then,
- Bob can save one vertex by picking a branch and marking its endpoint.
This reduces the length of the branch by 1. - Alice will also mark the endpoint of a branch - but this makes the rest of the branch unusable for Bob since none of its remaining vertices can now be saved.
So, once we have x_1, \ldots, x_k, Alice can delete any one element among them, while Bob can reduce one of them by 1.
In this new game, Bob’s aim is to maximize the number of moves he makes, while Alice’s aim is to minimize the number of moves Bob makes.
Now, Alice always needs k moves to delete every element - unless she can force Bob to also delete some elements for her; which can only happen with x_i = 1.
Naturally, this means it’s optimal for Alice to always remove large elements (to attempt to force Bob to operate on 1’s.), while similarly Bob will try to avoid subtracting from x_i = 1 when he can.
This means that the optimal strategy for both players is to just operate on the highest-valued element; i.e. Alice will delete the largest element while Bob reduces it by 1.
This process can simply be simulated to determine how many vertices Bob will save.
The simulation can be done in \mathcal{O}(N\log N) by storing all the x_i in a data structure that allows for quick insertion/deletion/finding maximum (sets or priority queues will work, for example), or even in \mathcal{O}(N) by using the fact that x_i \le N and they only decrease in value, so a sweep over the frequency array will work.
Finally, we need to prove that Alice can, in fact, stick to her optimal strategy while ensuring that Bob cannot save any heavy vertices.
To do this, if you look at the final greedy process from earlier it can be seen that:
- Among the branches with length \ge 2, Alice will surely have at least one vertex picked from every one of them.
- The branches with length 1 will be split halfway between Alice and Bob.
So, going back to the out-neighborhoods from the initial proof - if any out-neighbor is attached to a branch of length \ge 2, Alice will definitely pick some vertex from that branch; and so this out-neighborhood is automatically satisfied.
If every out-neighbor is a length 1 branch, then they’ll only start being picked towards the end of the process; and whenever Bob picks one of them the greedy allows for Alice to pick the other one (since all remaining branches must have length 1 at this point anyway.)
TIME COMPLEXITY:
\mathcal{O}(N) 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>());
for (int i = 0; i < n-1; ++i) {
int u, v; cin >> u >> v;
adj[--u].push_back(--v);
adj[v].push_back(u);
}
int root = 0;
while (root < n and adj[root].size() <= 2) ++root;
if (root == n) {
cout << n/2 - 1 << '\n';
continue;
}
vector par(n, -1);
auto dfs = [&] (const auto &self, int u) -> void {
for (int v : adj[u]) if (v != par[u]) {
par[v] = u;
self(self, v);
}
};
dfs(dfs, root);
vector freq(n+1, 0);
for (int i = 0; i < n; ++i) {
if (adj[i].size() != 1) continue;
int u = i, len = 1;
while (true) {
u = par[u];
if (adj[u].size() > 2) break;
++len;
}
++freq[len];
}
int ans = 0, ptr = n;
freq[0] = 1;
for (int i = 0; i < n; ++i) {
while (freq[ptr] == 0) --ptr;
if (ptr == 0) break;
if (i%2 == 0) {
--freq[ptr];
}
else {
--freq[ptr];
++freq[ptr-1];
++ans;
}
}
cout << n/2 - ans << '\n';
}
}