题解 CF1099F 【Cookies】
XG_Zepto
2019-01-10 22:09:04
### [Description](https://codeforces.com/contest/1099/problem/F)
Mitya 和 Vasya 在玩一个有趣的游戏。他们有一颗 $n$ 个节点，以 $1$ 为根的树。除了根之外的每一个节点 $i$，$p_i$ 是它父亲的编号。
对于树的每一个节点 $i$，它包含 $x_i$ 个曲奇，Mitya 需要 $t_i$ 的时间吃掉一块曲奇；在根节点有一块芯片，Mitya 可以花上 $l_i$ 的时间将它移至当前节点的任意一个儿子 $i$ 处。
Mitya 和 Vasya 将轮流进行如下操作（Mitya 先开始）：
- Mitya 将芯片向当前节点的儿子移动；
- Vasya 切断当前节点到一个儿子的连接。
Mitya 可以在轮到他的时候结束游戏，然后花时间将芯片移回根节点，并且顺路选择性地吃掉一些饼干。我们规定，整个流程（游戏开始到芯片回到根节点）的限时为 $T$。
求出在限定时间内，最坏情况下，Mitya 能吃掉曲奇的最大数量。
### Idea
我们从根开始 $DP$，最坏情况就是 Vasya 切断了最优的那个儿子，我们从次优的儿子处转移答案即可，计算答案只要考虑是否在当前节点折返。
我们用树状数组维护沿路上所有曲奇的消耗时间和数量，如果选择在当前节点折返，贪心地选择耗时最小的曲奇吃掉即可，这一步骤可以二分完成。
### Code
```cpp
#include <bits/stdc++.h>
#define mid ((l+r)>>1)
#define ll long long
#define maxn 100001
#define maxt 1000100
using namespace std;
int t[maxn],p[maxn];
int d[maxn],x[maxn];
vector<int> g[maxn];
ll ans[maxn];
ll T;int n;
struct BT{
ll t[maxn<<4];
void add(int x,ll v){while(x<maxt)t[x]+=v,x+=(x&-x);}
ll sum(int x){ll r=0;while(x) r+=t[x],x-=(x&-x);return r;}
}st,pt;
void Dfs(int u,ll dis){
ll cur=T-2*dis;
st.add(t[u],1ll*x[u]*t[u]);
pt.add(t[u],x[u]);
int l=0,r=maxt-1,res=0;
while(l<=r){
if (st.sum(mid)<=cur)
res=mid,l=mid+1;
else r=mid-1;
}
if (res)
ans[u]=pt.sum(res),
cur-=st.sum(res);
r=maxt-1,res=0;
while(l<=r){
if (pt.sum(mid)!=ans[u])
res=mid,r=mid-1;
else l=mid+1;
}
if (res) ans[u]+=cur/res;
for (auto v:g[u])
Dfs(v,dis+d[v]);
st.add(t[u],-1ll*x[u]*t[u]);
pt.add(t[u],-x[u]);
ll mx=0;int nxt=0;
for (auto v:g[u])
if (ans[v]>mx) mx=ans[v],nxt=v;
if (u==1) {ans[u]=max(ans[u],mx);return;}
mx=0;
for (auto v:g[u])
if (ans[v]>mx&&v!=nxt)
mx=max(mx,ans[v]);
ans[u]=max(ans[u],mx);
}
int main(){
cin>>n>>T;
for (int i=1;i<=n;++i)
cin>>x[i];
for (int i=1;i<=n;++i)
cin>>t[i];
for (int i=2;i<=n;++i)
cin>>p[i]>>d[i],
g[p[i]].push_back(i);
Dfs(1,0);
cout<<ans[1]<<endl;
return 0;
}
```