[APIO2012]派遣【左偏树】

左偏树】"/>

[APIO2012]派遣【左偏树】

>Link

luogu P1552

>Description

>解题思路

一个贪心的想法：对于每个节点，选择它的子树中 C C C最小的几个（直到它们的和超过了 M M M）使得个数最多，可以用堆来维护。在树上操作就需要把子树的堆合并起来了，但是直接合并肯定会超时，这时就要用到左偏树了。

左偏树：具有左偏性质的堆有序二叉树（右偏也行），父亲的键值比儿子都小（大）。
引入一个新的概念 d i s t dist dist，表示某个节点到它子树中的外节点的最近距离，外节点的定义为此节点至少有一个子树为空。左节点的 d i s t dist dist总比右节点大，这就是左偏性质。

左偏树可以做堆的操作，还可以合并堆、删除指定节点，这些都可以根据左偏树的性质完成。

>代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 100010
#define LL long long
using namespace std;struct edge
{int to, nxt;
} e[N];
int n, m, cnt, h[N], root, t[N], dfn[N], f[N], ls[N], rs[N], dist[N], siz[N];
LL val[N], c[N], sum[N], ans;void update (int now)
{sum[now] = sum[ls[now]] + sum[rs[now]] + val[now];siz[now] = siz[ls[now]] + siz[rs[now]] + 1;
}
void add (int u, int v)
{e[++cnt] = (edge){v, h[u]};h[u] = cnt;
}
int merge (int A, int B)
{if (!A) return B;if (!B) return A;if (val[A] < val[B]) swap (A, B);rs[A] = merge (rs[A], B);if (!ls[A] || dist[rs[A]] > dist[ls[A]]) swap (ls[A], rs[A]);update (A);if (!rs[A]) dist[A] = 0;else dist[A] = dist[rs[A]] + 1;return A;
}
int delroot (int now) {return merge (ls[now], rs[now]);}
void solve (int now)
{int u = now, v;t[now] = now;for (int i = h[now]; i; i = e[i].nxt){solve (v = e[i].to);t[u] = merge (t[u], t[v]);while (sum[t[u]] > m)t[u] = delroot (t[u]);}if (sum[t[u]] <= m)ans = max (ans, c[now] * (LL)siz[t[u]]);
}int main()
{int fa;scanf ("%d%d", &n, &m);for (int i = 1; i <= n; i++){scanf ("%d%lld%lld", &fa, &val[i], &c[i]);if (fa) add (fa, i);else root = i;sum[i] = val[i], siz[i] = 1;}solve (root);printf ("%lld", ans);return 0;
}