LT20-Editorial

editorial
,
1

Problem Link

Loop Through

Author: shail121

Difficulty

HARD

Prerequisites

Data Structures

Problem Statement

King Edward VIII's kingdom has m imperials. Each imperial has been given a unique ID number from 1 to m, where the King's ID is number 1. Every imperial in the kingdom has exactly one immediate chief — except the King, who has no supervisor. The hierarchy of King's Imperials forms a tree of IDs rooted at ID number 1 (the King).

The King decides to have a hideaway lasting for n days. Each day, the imperials will be assigned to different teams for building team spirit. Teams are constructed as following:

An imperial can invite their immediate chief(the King has no chief). If imperial a is invited by employee b, then a and b are considered to be in the same team.

Once an imperial is invited to be in a team, they are in that specific team i.e, If two imperials have the same immediate chief, only one of them can invite that chief to be in their team.

Every imperial must be in a team, even if they are the only one in it.

The palace where the king is hosting the hideaway has different pricing for each of the n days. For each day j, there is a cost of dj euros per team and a per-team size limit of pj .

Help the King find optimal teams for each day, so the cost of the n-day retreat is minimal, then print the total cost of the hideaway.

Approach

Naive Solution

For each p, we will calculate an array,ans.ansp will give us the minimum number of groups when the maximum size is less or equal to p.

How to do it for a p

Assume we'll choose some nodes so that there will be a chosen node in the subtree of each node that is at a distance of at most p to it. If we choose these nodes optimally, then the answer can be calculated.

We will use a priority queue. First, we’ll push all leaf nodes since all leaves must be taken. Our priority queue will give us the node with the maximum depth each time. In addition, we also keep a segment tree that can make range minimum queries and element assignment operations. Each time we choose a node, we’ll update its discover time by its depth. For all unchosen nodes, the segment tree will keep value inf.

Of course, every element we take from the queue doesn’t have to be chosen, but all chosen nodes must be from the queue. Now let’s look at what we do when we take some element from the queue. We will get a value, , from the segment tree with querying subtree of x. If t-depthx<p , then we don’t have to choose (so we’ll just delete it from the queue). Otherwise, node x must be chosen. We’ll increase ansp by 1 and update this node in the segment tree. Next, we’ll add the pth ancestor of this node (if it exists) to the queue. At this point, we’re done with x and delete it from the queue. When there are no elements left in the queue, the answer will be calculated.

Solution

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef pair < int, int > ii;

const int N = 1 << 17;
const int LOG = 17;

int n, m, tick, cnt;
int dep[N], st[N], nd[N], a[N], leaf[N];
vector < int > v[N], q[N];

int t[N << 1], sparse[LOG][N];

void up(int x, int k) {
t[x += N] = k;
while(x > 1) {
x >>= 1;
t[x] = min(t[x + x], t[x + x + 1]);
}
}

int get(int l, int r) {
int res = 1e9;
for(l += N, r += N; l <= r; l = (l + 1) >> 1, r = (r - 1) >> 1) {
if(l & 1) res = min(res, t[l]);
if(~r & 1) res = min(res, t[r]);
}
return res;
}

void dfs(int p, int x) {
st[x] = ++tick;
dep[x] = dep[p] + 1;
sparse[0][x] = p;
for(int i = 1; i < LOG; i++)
sparse[i][x] = sparse[i - 1][sparse[i - 1][x]];
leaf[x] = 1e9;
for(auto u : v[x]) {
dfs(x, u);
leaf[x] = min(leaf[x], leaf[u] + 1);
}
if(leaf[x] > 5e8) {
leaf[x] = 0;
cnt++;
}
q[leaf[x]].push_back(x);
nd[x] = tick;
}

int calc(int group) {
int res = cnt;
priority_queue < ii > Q;
for(auto x : q[group])
Q.push({dep[x], x});
vector < int > vv;
while(!Q.empty()) {
int x = Q.top().second;
Q.pop();
if(leaf[x] < group or get(st[x], nd[x]) - dep[x] < group)
continue;
vv.push_back(x);
up(st[x], dep[x]);
res++;
if(dep[x] > group) {
int k = group;
for(int i = LOG - 1; i >= 0; i–) {
if(k >= (1 << i)) {
k -= 1 << i;
x = sparse[i][x];
}
}
Q.push({dep[x], x});
}
}
for(auto x : vv)
up(st[x], 1e9);
return res;
}

int main () {

for(int i = 1; i < N + N; i++)
t[i] = 1e9;

scanf(“%d %d”, &n, &m);

for(int i = 2; i <= n; i++) {
int x;
scanf(“%d”, &x);
v[x].push_back(i);
}

dfs(0, 1);

for(int i = 1; i <= n; i++)
a[i] = calc(i);

ll ans = 0;

for(int i = 1; i <= m; i++) {
int x, y;
scanf(“%d %d”, &x, &y);
ans += (ll) x * a[min(n, y)];
ans %= (int) 1e9 + 7;
}

printf(“%lld\n”, ans);

return 0;

}