Codeforces1099F. Cookies【DP】【线段树】【贪心】【博弈】【沙比提（这是啥算法）】

LINK

---

题目大意

给你一棵树，每个节点上有一堆饼干

并且告诉你在每个节点上吃饼干吃一块需要多少时间

然后告诉你经过一条边的时间

总时间是T

两个人轮流进行，一个人向下选择子节点行走或者结束游戏并向上移动吃饼干，另一个人割断一条当前节点到儿子的边或者什么都不做

问第一个人可以吃到的最大的饼干的数量

思路

首先可以把边上的时间在dfs的时候抛掉

然后如果在一个节点上停了下来

我们考虑怎么统计吃的饼干，我们肯定会贪心选择需要时间最少的先吃，这样才能吃到尽量多块

然后用线段树（把单个时间当做下标）维护一下链上的所有信息

然后如果在这个节点不停下来，我们需要递归成子问题

显然第二个人会把往下走dp值最大的一个子树搞掉，所以当前的dp值就是往下走的第二大和停下来的max

在第一个节点特判一下就好了

---

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll N = 1e6 + 10; 

struct Node {

  ll v, w;

} p[N];

vector<Node> g[N];

ll n, T;

#define LD (t << 1)

#define RD (t << 1 | 1)

ll val[N << 2], siz[N << 2];

void insert(ll t, ll l, ll r, ll pos, ll cursiz) {

  val[t] += pos * cursiz;

  siz[t] += cursiz;

  if (l == r) return;

  ll mid = (l + r) >> 1;

  if (pos <= mid) insert(LD, l, mid, pos, cursiz);

  else insert(RD, mid + 1, r, pos, cursiz);

} 

ll query(ll t, ll l, ll r, ll vl) {

  if (l == r) return min(siz[t], vl / l);

  ll mid = (l + r) >> 1;

  if (val[LD] <= vl) return siz[LD] + query(RD, mid + 1, r, vl - val[LD]);

  else return query(LD, l, mid, vl);

}

ll dfs(ll u, ll lef) {

  insert(1, 1, 1e6, p[u].w, p[u].v);

  ll res = query(1, 1, 1e6, lef);

  ll f1 = 0, f2 = 0;

  for (auto now : g[u]) {

    ll v = now.v;

    if (lef <= now.w * 2) continue;

    ll cur = dfs(v, lef - now.w * 2);

    if (cur > f1) f2 = f1, f1 = cur;

    else if (cur > f2) f2 = cur;

  }

  insert(1, 1, 1e6, p[u].w, -p[u].v);

  if (u == 1) return max(res, f1);

  else return max(res, f2);

}

int main() {

  scanf("%lld %lld", &n, &T);

  for (ll i = 1; i <= n; i++) scanf("%lld", &p[i].v);

  for (ll i = 1; i <= n; i++) scanf("%lld", &p[i].w);

  for (ll i = 2; i <= n; i++) {

    ll u, w; scanf("%lld %lld", &u, &w);

    g[u].push_back((Node) {i, w});

  }

  printf("%lld", dfs(1, T));

  return 0;

}