PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
DFS, Sorting
PROBLEM:
You are given a tree with one person standing at each vertex. Person has strength P_i, all P_i are distinct.
The following process repeats:
- The person at the root leaves the tree.
- Then, as long as there’s an empty vertex with some child that isn’t empty, the person with maximum strength from a child will move one step up.
You’re at vertex N with strength K.
Find the minimum possible time that you can leave the tree.
EXPLANATION:
Let the path from vertex 1 to vertex N be 1 = v_1, v_2, \ldots, v_m = N.
Every second, we can move at most one step along this path. So, given that there are m vertices on this path, at best we need m seconds to leave the tree.
Let’s try to analyze when exactly m seconds will be enough.
Call vertices u and v siblings if they share the same parent.
Then,
- All the siblings of N must have a lower strength than P_N (which is K) - otherwise, one of them will move up before N.
- All the siblings of v_{m-1} (which is the parent of N) must have a lower value than P_{v_{m-1}}, otherwise v_{m-1} will be delayed (and that indirectly delays N as well).
Further, all the siblings of v_{m-1} must also have a lower value than P_N; since after P_N has moved up once, it’ll be compared with the siblings of v_{m-1} for the next movement. - Similar reasoning shows that the siblings of v_{m-2} must have smaller values than all three of P_{v_{m-2}}, P_{v_{m-1}}, P_N.
More generally, the siblings of P_{v_i} must have smaller values than P_{v_j} for all j \gt i.
Now, we’re free to choose the strengths at the vertices. Let’s try to utilize that freedom.
Let s denote the total number of siblings of all the vertices v_1, v_2, \ldots, v_m.
If s \leq K-1, then we can always guarantee that there will be no delays - since we can give the values 1, 2, 3, \ldots, s to the siblings, and then assign the remaining values however we want.
This way, all the siblings of all the nodes on the path will have values \leq s, while all other vertices will have values \gt s.
This ensures that every second, all vertices on the 1\to N path will move one step upward; and so N will leave at time m, which is optimal.
The issue is instead when s \gt K-1, so we can’t give “small” values to every sibling of the path anymore.
This guarantees that at some point of time, N will be delayed by another vertex.
Note that we can in fact guarantee that the vertices other than N on the path will never be delayed, by giving them the values N, N-1, N-2, \ldots so that they’re definitely larger than anything outside the path.
So, we only need to worry about N itself being delayed, and not any of its ancestors.
Now, suppose N is delayed by vertex u - that is, u is a sibling of some v_i and P_N \lt P_u.
Then, N will be delayed by the entire subtree of u.
Why?
Suppose N is delayed by u, but not by something in the subtree of u.
That would mean this “something” in the subtree of u has a value that’s less than K.
But then we could’ve simply assigned this smaller value to u itself, and avoided being delayed by u itself.
So, if we cannot avoid being delayed by a node, we also will be delayed by its entire subtree.
So, for each sibling vertex of the path, either N won’t get delayed by it at all, or N will get delayed by the entire subtree.
Using the values 1 through K-1, we can ensure that N isn’t delayed by K-1 vertices.
Clearly, it’s best to choose whichever K-1 vertices have the largest subtree sizes among the siblings.
The time at which N will leave the tree is then m plus the sum of subtree sizes of the remaining s - (K-1) siblings.
All of this can be implemented in \mathcal{O}(N \log N), requiring only a DFS to find subtree sizes + map the path and find siblings.
The complexity is dominated by the \mathcal{O}(N\log N) of sorting subtree sizes.
TIME COMPLEXITY:
\mathcal{O}(N \log 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, x; cin >> n >> x;
vector adj(n+1, vector<int>());
for (int i = 1; i < n; ++i) {
int u, v; cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
vector<int> par(n+1), children(n+1), subsz(n+1);
auto dfs = [&] (const auto &self, int u, int p) -> void {
par[u] = p;
subsz[u] = 1;
for (int v : adj[u]) if (v != p) {
self(self, v, u);
subsz[u] += subsz[v];
++children[u];
}
};
dfs(dfs, 1, 0);
if (x == 1) {
cout << n - subsz[n] + 1 << '\n';
continue;
}
auto solve = [&] () {
vector<int> onpath(n+1);
int important = 0;
{
int cur = n;
while (cur > 1) {
onpath[cur] = 1;
important += children[par[cur]] - 1;
cur = par[cur];
}
onpath[cur] = 1;
}
if (important >= x - 1) {
// Distribute small values to the important nodes with largest subtree sizes
vector<int> subsizes;
for (int i = 2; i < n; ++i) {
if (!onpath[i] and onpath[par[i]] and par[i] != n) {
subsizes.push_back(subsz[i]);
}
}
sort(rbegin(subsizes), rend(subsizes));
int delay = accumulate(begin(subsizes) + x-1, end(subsizes), 0);
cout << accumulate(begin(onpath), end(onpath), 0) + delay << '\n';
return;
}
// Other case: there's enough small things
// Answer is just number of vertices on the path
cout << accumulate(begin(onpath), end(onpath), 0) << '\n';
};
solve();
}
}