[apio2012] dispatch

Init - Cherry Blossoms 2021-09-15 09:25:24

The question

Selecting some nodes in a rooted tree maximizes the product of their cost and the number of selected nodes and the leadership of one of their common ancestors under the condition that they do not exceed a certain value .

analysis

Even if the first thought is greed , After playing with our hands, we can also naturally think of trees dp.

Then we consider how to transfer the information of the child node to the current node .

We set up \(dp_x\) Expressed in \(x\) The optimal solution in the subtree of the root .

So when merging up , There are obviously two situations :

  1. The administrator is in the child node of the current node

  2. The current node is an administrator .

Set the set of child nodes of the current node as \(y\).

For the first case, we directly take \(max_{i \in y}(dp_i)\).

In the second case , Because leadership is fixed \(L_x\), Obviously, we should select nodes from small to large according to the cost in the subtree with the current node as the root , Get the most people , In this way, the optimal .

Now suppose we can find the maximum number of people in an acceptable time , We have the following state transition equation :

\[dp_x = max(people_{max} \times L_x, max_{i \in y}(dp_i)) \]

So the problem we need to solve now is how to quickly find this \(people_{max}\).

Obviously, this is a data structure that can support rapid merging and access to the most valuable data .

It's not hard to think of left leaning trees and balanced trees .

According to our previous search \(people_{max}\) The strategy of , The first thing I thought about was the small root pile , But accessing the next element like this is \(log\) Of , And write on the top pile . Then consider the balanced tree , But the merging operation will greatly increase our time .

So we need to change our thinking .

I didn't think of this when I was doing it , Plus I'm here to practice left leaning trees , So what I think is how to optimize the method of maintaining the left leaning tree .

It is not difficult to find that the limitation of the above method is that we must delete the top element when accessing the next element , But it's not really deleted , Because this part is what we need , So write on the top pile , But the time complexity is false again .

If it's hard, it's hard , We consider maintaining a large root heap , Record the sum in the heap , If the sum is greater than the budget , So let's delete the top element , Then the rest must be the most , This means the same as our previous strategy . As for the deleted , Because after our upward merger , When updating the optimal solution , Our optimal solution must be the optimal solution re selected from the set of optimal solutions in each subtree . So obviously, the deleted nodes , It is impossible to be selected in the process of merging and updating answers up . So we can ignore the deleted nodes .

Because each node will be deleted at most once , The merging of left leaning trees is \(logn\) Grade , So the whole maintenance \(people_max\) The process is \(nlogn\) Of .

And tree dp The process is \(O(n)\) Grade ( Because the number of sides is \(n\) Grade ), So the total time is \(O(nlogn)\) Grade .

However, the left leaning tree of this problem should be added and searched to ensure the time complexity , Otherwise, a single operation will be stuck \(O(n)\).

Code

#include<cstdio>
#include<iostream>
#include<cctype>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
struct Leftist {
int val[N], dis[N], ls[N], rs[N], rt[N];
Leftist () { dis[0] = -1; }
inline void swap(int &x, int &y) { x ^= y ^= x ^= y; }
int merge(int x, int y) {
if(!x || !y) return x | y;
if(val[x] < val[y] || (val[x] == val[y] && x > y)) swap(x, y);
rs[x] = merge(rs[x], y);
if(dis[rs[x]] > dis[ls[x]]) swap(rs[x], ls[x]);
dis[x] = dis[rs[x]] + 1;
return x;
}
inline int pop(int x) { return rt[ls[x]] = rt[rs[x]] = rt[x] = merge(ls[x], rs[x]); }
inline int Find(int x) { return x == rt[x] ? x : rt[x] = Find(rt[x]); }
}tr;
int n, m, rt, a[N], L[N], siz[N]; LL dp[N], sum[N];
int head[N], nex[N << 1], to[N << 1], tot = 1;
inline void add(int u, int v) {
nex[++tot] = head[u], to[tot] = v, head[u] = tot;
nex[++tot] = head[v], to[tot] = u, head[v] = tot;
}
void dfs(int x, int f) {
sum[x] = a[x]; siz[x] = 1;
for(int i = head[x], y; i; i = nex[i]) {
y = to[i];
if(y == f) continue;
dfs(y, x);
siz[x] += siz[y], sum[x] += sum[y];
int f1 = tr.Find(x), f2 = tr.Find(y);
if(x != y) tr.rt[f1] = tr.rt[f2] = tr.merge(f1, f2);
dp[x] = max(dp[x], dp[y]);
}
int root = tr.rt[tr.Find(x)];
while(sum[x] > m) sum[x] -= tr.val[root], siz[x]--, root = tr.pop(root);
dp[x] = max(dp[x], 1LL * siz[x] * L[x]);
}
inline void read(int &x) {
x = 0; int c = getchar();
for(; !isdigit(c); c = getchar());
for(; isdigit(c); c = getchar())
x = x * 10 + c - 48;
}
int main() {
read(n), read(m);
for(int i = 1, f; i <= n; i++) {
read(f), read(a[i]), read(L[i]);
if(!f) rt = i; else add(f, i);
}
for(int i = 1; i <= n; i++) tr.val[i] = a[i], tr.rt[i] = i;
dfs(rt, 0);
printf("%lld\n", dp[rt]);
return 0;
}
Please bring the original link to reprint ,thank
Similar articles

2021-09-15

2021-09-15

2021-09-15

2021-09-15