LYDSY 2809
题目大意
暂无
题目解法
暂无
RTFC
#include <cctype>
#include <cstdio>
template <typename T> inline void swap(T &x, T &y)
{
T t = x;
x = y;
y = t;
}
template <typename T> inline T max(T x, T y) { return x > y ? x : y; }
inline void read(int &x)
{
int ch = x = 0;
while (!isdigit(ch = getchar()));
for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
}
const int maxn = 100010;
int n, m, fa[maxn], C[maxn], L[maxn], cnt;
typedef struct Node
{
Node *lc, *rc;
int val, dis, sz;
long long sum;
} *lpNode;
lpNode merge(lpNode x, lpNode y)
{
if (x == 0) return y;
if (y == 0) return x;
if (x->val < y->val) swap(x, y);
x->rc = merge(x->rc, y);
if (x->lc == 0 || x->lc->dis < x->rc->dis) swap(x->lc, x->rc);
x->dis = x->rc ? x->rc->dis + 1 : 0;
x->sz = (x->lc ? x->lc->sz : 0) + (x->rc ? x->rc->sz : 0) + 1;
x->sum = (x->lc ? x->lc->sum : 0) + (x->rc ? x->rc->sum : 0) + x->val;
return x;
}
Node mem[maxn];
lpNode nodes[maxn];
int head[maxn], to[maxn], next[maxn], ecnt, arr[maxn], aend;
inline void addEdge(int f, int t)
{
ecnt++;
next[ecnt] = head[f];
head[f] = ecnt;
to[ecnt] = t;
}
int main()
{
read(n), read(m);
for (int i = 1; i <= n; i++)
read(fa[i]), read(C[i]), read(L[i]), addEdge(fa[i], i),
(nodes[i] = mem + i)->sz = 1, nodes[i]->sum = nodes[i]->val = C[i];
for (int i = 0; i <= n; i++)
for (int cur = head[i]; cur; cur = next[cur])
arr[++aend] = to[cur];
long long ans = 0;
for (int i = aend; i; i--)
{
int x = arr[i], y = fa[x];
ans = max(ans, 1ll * nodes[x]->sz * L[x]);
nodes[y] = merge(nodes[y], nodes[x]);
while (y && nodes[y]->sum > m)
nodes[y] = merge(nodes[y]->lc, nodes[y]->rc);
}
printf("%lld", ans);
return 0;
}