PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: aryandutt
Tester: yash_daga
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
DFS
PROBLEM:
On a tree with K leaves, the following game is played.
- K people start at node 1, each one will move toward a distinct leaf.
- Chef starts at some leaf node of his choice, and can move to any adjacent node; however, he will make his move only after all the others have moved.
- Chef tags a person if they share a non-leaf node.
If Chef moves optimally, what’s the maximum number of people who can be tagged?
EXPLANATION:
Clearly, it’s always optimal for Chef to move upwards: remaining at the same node or moving downwards don’t really improve the number of people that can be tagged.
Further, note there will exist some node u such that Chef catches exactly those people who must go into the subtree of u.
In particular,
- If Chef can reach a node u before (or at the same time) as the people who must pass through it, he can catch all of them.
- If Chef cannot reach node u fast enough, he can never catch all of these people — they will reach u before Chef does, then move out of it by splitting into their subtrees; so Chef can at best capture some subset of them.
Suppose we know for each node u the following values:
- \text{dep}[u], the depth of node u from the root.
Note that this is the time taken to reach node u from the root. - \text{mn}[u], the minimum time needed for Chef to start at some leaf and reach u using only upward moves.
- \text{leaves}[u], the number of leaves in the subtree of u.
Then, the answer is the maximum of \text{leaves}[u], across all those u such that \text{mn}[u] \leq \text{dep}[u].
Now, what exactly is \text{mn}[u]?
For Chef to reach u in the minimum time, it’s clearly optimal to start at some leaf in the subtree of u that has minimum depth.
We’re already computing depths, so this isn’t hard to maintain.
Perform a DFS, starting at node 1 (which has depth 0).
When at node u, do the following:
- For each child c of u, set \text{dep}[c] = \text{dep}[u] + 1.
Then, recursively perform the DFS on c. - Once the children have been processed, we have:
- if u is itself a leaf, \text{leaves}[u] = 1 and \text{mn}[u] = 0.
- Otherwise, \text{leaves}[u] is the sum of all \text{leaves}[c], and \text{mn}[u] is the minimum among all \text{mn}[c], plus 1.
- Finally, we check if u is “good” — that is, if \text{mn}[u] \leq \text{dep}[u].
If it is, set \text{ans} \gets \max(\text{ans}, \text{leaves}[u]); otherwise do nothing.
Note that Chef cannot catch people at leaves, so this check is only to be done at non-leaves.
We do a single DFS, so the solution is linear.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (C++)
// #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-1].push_back(v-1);
adj[v-1].push_back(u-1);
}
vector<int> mnleaf(n, n), leafct(n);
int ans = 0;
auto dfs = [&] (const auto &self, int u, int p, int dep) -> void {
bool leaf = true;
for (int v : adj[u]) if (v != p) {
self(self, v, u, dep + 1);
leaf = false;
mnleaf[u] = min(mnleaf[u], mnleaf[v]);
leafct[u] += leafct[v];
}
if (leaf) mnleaf[u] = dep, leafct[u] = 1;
if (!leaf and mnleaf[u] <= 2*dep) ans = max(ans, leafct[u]);
};
dfs(dfs, 0, 0, 0);
cout << ans << '\n';
}
}