CF1099F Cookies_牛客博客

本题解同步发布于[本场 $\mathrm{CF}$ 总题解](https://www.luogu.org/blog/expect2004/CF530Div2)，欢迎来踩。

F - Cookies

这题在考试时间内有了正确的思路但没有写完。。。

$\mathrm{Vasya}$ 的策略

题目的表述中， $\mathrm{Vasya}$ 是可以随便剪断当前标记所在结点 $x$ 到任意一棵子树的。

但是题目要求我们求的是最坏情况下的最小值，我们可以只考虑 $\mathrm{Vasya}$ 创造了最坏的条件，即剪掉了本来可以取到最优解的子树。

树形 $\mathrm{DP}$

首先做一次 $\mathrm{DP}$ ，求出 $\mathrm{Vasya}$ 不剪时的最优解，同时记录取到最优解的位置。

接下来标记不得进入之前最优解的位置，再做一次 $\mathrm{DP}$ 。

这两次 $\mathrm{DP}$ 等价于维护了每个结点的最优解和次优解。

在 $\mathrm{DP}$ 的过程中使用了贪心的思想，显然从根到 $x$ 的路径上，尽量吃花费时间少的饼干。

维护饼干

我一开始是想通过 $\mathrm{vector}$ 或者 $\mathrm{Heap}$ 来维护的，可是发现这样不太好实现，并且在链的情况下复杂度会退化为 $O(n^2)$ 。

我太菜了并不会多少数据结构，于是自然而然想到使用树状数组来维护，树状数组的下标为 $t$ ，插入的值为饼干数目。

然后二分 $t$ 就行了。

code:

#include<bits/stdc++.h>
using namespace std;

#define int long long
#define maxn 100003
int n,T;
int x[maxn],t[maxn];
int Head[maxn],tot,Next[maxn],to[maxn],w[maxn];
int aa,bb;
int ans[maxn];
int fake;
template<typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-'){
        ch=getchar();fh=-1;
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

struct BIT{
    #define lowbit(x) (x&(-x))
    int c[1001003];
    void add(int x,int k){
        while(x<=1001000){
            c[x]+=k;x+=lowbit(x);
        }
    }
    int query(int x){
        int re=0;
        while(x){
            re+=c[x];x-=lowbit(x);
        }
        return re;
    }
}a,b;

void add(int x,int y,int z){
    to[++tot]=y,Next[tot]=Head[x],Head[x]=tot,w[tot]=z;
}

int erfen(int fa){
    int l=0,r=1000000,mid,re=0;
    while(l<=r){
        mid=(l+r)>>1;
        if(a.query(mid)<=fa) re=mid,l=mid+1;
        else r=mid-1;
    }
    fake=l;
    return re;
}

int find(int node){
    int l=fake,r=1000000,re=0,mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(b.query(mid)!=ans[node]) re=mid,r=mid-1;
        else l=mid+1;
    }
    return re;
}

void dfs(int node,int dis){
    int rest=T-2*dis;
    a.add(t[node],x[node]*t[node]);
    b.add(t[node],x[node]);
    int flag=erfen(rest);
    if(flag) ans[node]=b.query(flag),rest-=a.query(flag);
    flag=find(node);
    if(flag) ans[node]+=rest/flag;
    for(int i=Head[node];i;i=Next[i]){
        dfs(to[i],dis+w[i]);
    }
    a.add(t[node],-x[node]*t[node]);
    b.add(t[node],-x[node]);
    int mx=0,del=0;
    for(int i=Head[node];i;i=Next[i]){
        if(ans[to[i]]>mx){
            mx=ans[to[i]],del=to[i];
        }
    }
    if(node==1){
        ans[node]=max(ans[node],mx);
        return;
    }
    for(int i=Head[node];i;i=Next[i]){
        if(to[i]==del) continue;
        ans[node]=max(ans[node],ans[to[i]]);
    }
}

int main(){
    read(n);read(T);
    for(register int i=1;i<=n;i++){
        read(x[i]);
    }
    for(register int i=1;i<=n;i++){
        read(t[i]);
    }
    for(register int i=2;i<=n;i++){
        read(aa);read(bb);
        add(aa,i,bb);
    }
    dfs(1,0);
    printf("%I64d\n",ans[1]);
    return 0;
}