hello.

题解 CF1099F 【Cookies】

2019-01-10 22:09:04


Description

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

#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;
}