"APIO2012" and "Luogu P1552" dispatch

Description

In this gang, there is a ninja called Master. Except Master, every Ninja has only one superior. In order to keep secrets and enhance the leadership of ninjas, all instructions related to their work are always sent by their superiors to their direct subordinates, and are not allowed to be sent by other means.

Now you need to recruit a group of ninjas and send them to customers. You need to pay a certain salary for each dispatched ninja, and make the total salary not exceed your budget. In addition, in order to send instructions, you need to select a ninja as the manager. The manager is required to send instructions to all dispatched ninjas. When sending instructions, any Ninja (whether dispatched or not) can be used as the messenger. The manager may or may not be assigned. Of course, if the manager is not dismissed, you don't have to pay the manager's salary.

Your goal is to maximize customer satisfaction within your budget. Here, customer satisfaction is defined as the total number of dispatched ninjas multiplied by the leadership level of the manager, and the leadership level of each Ninja is also certain.

Write a program to give the superior \ (b\u i\), salary \ (c\u i\), leadership \ (l\u i\), and the total salary budget paid to the Ninjas \ (M\), and output the maximum value of customer satisfaction when the above requirements are met within the budget.

Hint

  • \(1 ≤ n ≤ 10^5\) number of ninjas;

  • \(1 ≤ m ≤ 10^9\) total salary budget;

  • \(0 ≤ b_i < i\) the number of Ninja's superior;

  • \(1 ≤ C_i ≤ M\) Ninja's salary;

  • \(1 ≤ l\u I ≤ 10^9\) Ninja leadership level.

  • For the data of the previous \ (30\%\), \ (n ≤ 3\times 10^3\).

Solution

Obviously, the working relationship of Ninja forms a tree structure.

Then the problem can be formalized as follows: select as many nodes as possible in each subtree so that the total cost of these nodes does not exceed \ (m\). Finally, merge the answers of all subtrees.

It is not difficult to think of starting from the leaf node and maintaining the Ninja set with an appropriate data structure.

Whenever a point is reached, first merge the current set to the superior, and adjust the superior set so that the Ninja cost no more than \ (m\) and the set is as large as possible.

We greedily think that as long as we pop up the Ninjas that cost a lot each time, because the answer only involves the leadership of the roots and the number of ninjas.

After one point is completed, you can directly use your superior to update the answer.

For collection maintenance, we need an appropriate data structure that supports deletion of maximum values and efficient consolidation. Here, select the left leaning tree.

As for the complexity, since each Ninja will only pop up once, the time complexity is \ (O(n\log n) \).

Code

#include <algorithm>
#include <iostream>

using namespace std;
const int N = 1e5 + 5;

struct ninja {
	int fa, cost, lead;
} nj[N];
int n, m;

struct ltNode {
	int ch[2], val, dist, rt;
} t[N];
#define lc t[x].ch[0]
#define rc t[x].ch[1]

int merge(int x, int y) {
	if (!x || !y) return x | y;
	if (t[x].val < t[y].val) swap(x, y);
	rc = merge(rc, y);
	if (t[lc].dist < t[rc].dist) swap(lc, rc);
	t[x].rt = t[lc].rt = t[rc].rt = x;
	t[x].dist = t[rc].dist + 1;
	return x;
}
int findrt(int x) {
	return x == t[x].rt ? x : t[x].rt = findrt(t[x].rt);
}

struct LefTr {
	int root;
	int size;
	long long sum;
	inline void join(LefTr t) {
		size += t.size, sum += t.sum;
		root = merge(root, t.root);
	}
	inline void pop() {
		sum -= t[root].val;
		root = merge(t[root].ch[0], t[root].ch[1]);
		--size;
	}
} lt[N];

void init() {
	for (register int i = 1; i <= n; i++) {
		lt[i].root = t[i].rt = i;
		lt[i].size = 1;
		lt[i].sum = t[i].val = nj[i].cost;
	}
}

signed main() {
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for (register int i = 1; i <= n; i++)
		cin >> nj[i].fa >> nj[i].cost >> nj[i].lead;
	init();
	
	long long ans = 0ll;
	for (register int i = 1; i <= n; i++)
		ans = max(ans, nj[i].lead * 1LL);
	
	for (register int i = n; i > 1; i--) {
		int f = nj[i].fa;
		lt[f].join(lt[i]);
		while (lt[f].sum > m) lt[f].pop();
		ans = max(ans, lt[f].size * 1LL * nj[f].lead);
	}
	
	cout << ans << endl;
	return 0;
}

Tags: data structure

Posted by Penelope on Tue, 31 May 2022 12:43:21 +0530