PROBLEM LINK:
Author: Murugappan
Editorialist: Murugappan
DIFFICULTY:
Hard
PREREQUISITES:
DP, Graphs.
PROBLEM:
The problem when rephrased without story, looks as follows.
We have a rooted tree with maximum height of 60 with each edge representing a unit distance and each node has some non-negative value associated with it.
We have to select a subset of nodes which are still connected and the sum of their values \ge k and the ceil(radius) of the selected subtree is as minimum as possible.
EXPLANATION:
Let’s solve the trivial case first
When does the solution ceases to exist?
The solution doesn’t exists only when the sum of all the value of the given tree is less than K. This case could be easily solved as we can just sum up the values while reading the input.
Complexity: O(n)
So in all other cases solution exists.
If you visualize how the subtree could be, it can be of any possible orientation need not be an entire subtree rooted at a particular node.
So the approach is to fix a particular node as the center of subtree about to be selected and try to find the best possible answer (if exists). Do this for all possible center and get the best possible answer. This would have a time complexity of O(N * \text {complexity for each center}).
Now the problem boils down to the following.
Given a particular node which would act as the center find the best possible solution (if exists).
Let’s assume that we have the following DP table available to us.
DP[i][j] denotes that the sum of values of all nodes in the subtree rooted at i which are at most at distance j from node i.
Given node i as center and j to be the ceil(radius) of the subtree to be extracted then the max value of each possible radius(j) is as follows.
| Center | Radius | Max value |
|---|---|---|
| i | 0 | DP[i][0] |
| i | 1 | DP[i][1]+DP[parent(i)][0] |
| i | 2 | DP[i][2] + (DP[parent(i)][1]-DP[i][0]) + (DP[parent(parent(i))][0]) |
| i | x | DP[i][x] + (DP[parent(i)][x-1]-DP[i][x-2]) + (DP[parent(parent(i))][x-2]-DP[parent(i)][x-3])… |
The interpretation of the above table is as follows.
For a center node (i) with max radius X, we take the following nodes
- All nodes in the subtree of i with distance at most X from i.
- All nodes in the subtree of parent of i with distance at most x-1 from parent of i (or distance at most X from i).
- …….
So given a center (i) and radius (x) we can find the value in O(x).
So finding the best possible solution given a center would be 1+2+3+4…..+max_{radius} = O(max_{radius}^2)
As from the question the max_{radius} is limited to 60.
Can we do better?
Yes of course.
For a given center instead of iterating over all possible radius we can do binary search.
But what is monotonic here?
If we are able to find a radius (x) whose tree value is v then for any radius (y) such that y>x the value would be >= v.
We need to find the min radius.
So instead of O(max_{radius}^2) it would be O(max_radius*log(max_{radius})).
So the overall complexity to solve the problem is O(N*60*log(60)).
Wait! Is it over?
Not yet. We assumed that we had the DP table ready. How do we build that?
It can be built through dfs. The recursion is DP[i][j]= Value(i) + sum(DP[x][j-1]) where x is immediate child of i.
This computation takes O(N*max_{radius}).
SOLUTION:
Setter's Solution
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define x first
#define y second
#define fastread ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define PI (atan(1)*4)
#define mp make_pair
using namespace std;
//test_specific contents
const int maxn = 1e5, maxlevel = 60;
vector<int> adjlist[maxn];
ll dp[maxn][maxlevel], k, sum_of_val;
int n, root, parent[maxn];
void dfs(int cur, int par) {
parent[cur] = par;
for (int i = 1; i < maxlevel; i++)
dp[cur][i] = dp[cur][0];
for (auto u : adjlist[cur]) {
if (u == par)
continue;
dfs(u, cur);
for (int i = 1; i < maxlevel; i++) {
dp[cur][i] += dp[u][i - 1];
}
}
for (int i = 1; i < maxlevel; i++)
dp[cur][i] = max(dp[cur][i], dp[cur][i - 1]);
}
void clear() {
memset(dp, 0, sizeof(dp));
for (int i = 0; i < maxn; i++)
adjlist[i].clear();
sum_of_val = 0;
}
ll get_value(int center, int radius) {
ll value = dp[center][radius];
int cur = center;
while (parent[cur] != -1 && radius != 0) {
value += dp[parent[cur]][radius - 1];
if ((radius - 1) != 0)
value -= dp[cur][radius - 2];
cur = parent[cur];
radius--;
}
return value;
}
ll get_best(int radius) {
ll best = 0;
for (int i = 0; i < n; i++) {
best = max(best, get_value(i, radius));
}
return best;
}
int bsrch(int l, int r) {
if (l == r)
return l;
int mid = (l + r) / 2;
if (get_best(mid) >= k)
return bsrch(l, mid);
else
return bsrch(mid + 1, r);
}
void solve() {
clear();
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> dp[i][0];
sum_of_val += dp[i][0];
}
cin >> root;
for (int i = 1; i < n; i++) {
int x, y;
cin >> x >> y;
adjlist[x].pb(y);
adjlist[y].pb(x);
}
dfs(root, -1);
if (sum_of_val < k) {
// answer does not exist
cout << -1 << endl;
return;
}
ll ans = bsrch(0, maxlevel);
cout << ans << endl;
}
//end of test_specific contents
int main()
{
srand(time(NULL));
solve();
return 0;
}