Codeforces 1099F
题意：一棵 $n$ 个节点，以 $1$ 为根的带边权树，每个点包含 $x_i$ 个曲奇， 需要 $t_i$ 的时间吃掉一块曲奇。有两个人Mitya和Vasya在轮流玩游戏，Mitya先手。在根处有一个小动物，Mitya每次可以选择花费边权$l_i$的时间来到达当前点的孩子节点或者直接结束游戏，从这里返回选择性吃一些曲奇。Vasya 切断当前节点到一个儿子的连接(可以不一定要切)。整个游戏限时为 $T$
求最坏情况下能吃到的曲奇个数。
这题比较麻烦……可以发现我们不用模拟整个过程，直接在往下的过程中路程乘二，然后直接吃曲奇即可。而且我们尽量要在花费最小的位置吃曲奇。那么当前节点位置到根上的曲奇都可以作为候选。那么我们可以用数据结构维护曲奇。
我们先忽略掉 Vasya，即不考虑断边的情况，设$f(u)$为根到$u$的不考虑断边下的最优解。
我们要尽量多吃曲奇，那么我们尽量要在花费最小的位置吃曲奇，所以我们不妨维护一个值域在$t$上的一个树状数组，记录值为$t_i \cdot x_i$，这个树状数组上的前缀和即为最优吃曲奇的时间，我们在树状数组上二分找到一个位置使得其是$\leq T - 2 \cdot S$的最大值，其中$S$为从根到该位置的路径长度。这样找到的一定是最优的。因为值域从$1,2,3,\cdots,maxt$排序。为了统计到底有多少个曲奇能吃，那么再开一个值域在$t$上的一个树状数组，记录值为$x_i$，那么前缀和就是有多少个曲奇。最后还需要补不足够部分的曲奇，具体看代码实现，小技巧是有余数要补的可以方便化直接减一，这样整除就不用讨论。
然后考虑 Vasya，Vasya 一定断开获益最大的一条边，所以 Mitya 只能取到次优值。
设$dp(u)$为$u$为子树，考虑断边的最优值，$maxd(u), cid(u)$分别为$u$为子树不包括$u$，考虑断边的最优值的次优值。
如果当前是根，那么$dp(1)=max(f(1), maxd(1))$，因为 Mitya 先手
否则只能取到次大值，则$dp(u)=max(f(u), cid(u))$
$maxd(u)$和$cid(u)$用次大值的更新方法来更新即可。用子树的$dp$值来更新。
真是一个数据结构+DP好题。。
知识点：
有余数要补的可以方便化直接减一，这样整除就不用讨论
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MAXN = 100000 + 5;
struct edge {
LL v, w, nxt;
} ed[MAXN * 2];
LL n, T, x[MAXN], t[MAXN], hd[MAXN], en;
LL t_bit[1000000 + 5], tx_bit[1000000 + 5], maxt;
LL f[MAXN], dp[MAXN], maxd[MAXN], cid[MAXN];
void ins(LL u, LL v, LL l) {ed[++en] = (edge){v, l, hd[u]}, hd[u] = en;}
LL lowbit(LL x) {return x & (-x);}
void t_add(LL x, LL v) {
for (LL i = x; i <= maxt; i += lowbit(i)) t_bit[i] += v;
}
void tx_add(LL x, LL v) {
for (LL i = x; i <= maxt; i += lowbit(i)) tx_bit[i] += v;
}
LL t_query(LL x) {
LL ret = 0;
for (LL i = x; i > 0; i -= lowbit(i)) ret += t_bit[i];
return ret;
}
LL tx_query(LL x) {
LL ret = 0;
for (LL i = x; i > 0; i -= lowbit(i)) ret += tx_bit[i];
return ret;
}
void dfs_ign(LL u, LL fa, LL D) { // 忽略 Vasya 的答案
t_add(t[u], x[u]);
tx_add(t[u], x[u] * t[u]);
LL l = 1, r = maxt + 1;
while (l < r) {
LL mid = (l + r) >> 1ll;
LL val = tx_query(mid);
if (val < T - 2ll * D) l = mid + 1; else r = mid;
}
LL k = l - 1; // 有余数要补的可以方便化直接减一，这样整除就不用讨论
f[u] = t_query(k);
if (k != maxt) f[u] += (T - 2ll * D - tx_query(k)) / (k + 1);
for (LL i = hd[u]; i >= 0; i = ed[i].nxt) {
edge &e = ed[i];
if (e.v != fa) dfs_ign(e.v, u, D + e.w);
}
t_add(t[u], -x[u]);
tx_add(t[u], -x[u] * t[u]);
}
void dfs_dp(LL u, LL fa) {
for (LL i = hd[u]; i >= 0; i = ed[i].nxt) {
edge &e = ed[i];
if (e.v != fa) {
dfs_dp(e.v, u);
if (dp[e.v] > maxd[u]) {
cid[u] = maxd[u];
maxd[u] = dp[e.v];
} else if (dp[e.v] > cid[u]) cid[u] = dp[e.v];
}
}
if (u == 1) dp[u] = max(f[u], maxd[u]);
else dp[u] = max(f[u], cid[u]);
}
void clean() {
maxt = 0, en = -1, ms(hd, -1);
ms(t_bit, 0), ms(tx_bit, 0);
ms(f, 0), ms(dp, 0), ms(maxd, 0), ms(cid, 0);
}
int solve() {
clean();
scanf("%lld%lld", &n, &T);
for (LL i = 1; i <= n; ++i) scanf("%lld", &x[i]);
for (LL i = 1; i <= n; ++i) scanf("%lld", &t[i]), maxt = max(maxt, t[i]);
for (LL p, l, i = 2; i <= n; ++i) {
scanf("%lld%lld", &p, &l);
ins(i, p, l), ins(p, i, l);
}
dfs_ign(1, 0, 0);
dfs_dp(1, 0);
cout << dp[1];
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}
