一道题变两道题。。。

由于父亲会影响到儿子,那么就要分情况讨论了。

对于前$50pts$,$c_i\le 1$。

设$f_i$表示$i$在父亲之后激发,$g_i$表示$i$在父亲之前激发。

状态无关于它的子树,因此对于$i$子树来讲,$f_i,g_i$是可以互相转换的。

通过这个可以发现,$g_i-f_i\le 1$,这个等号仅在$c_{fa}=1$时成立,意思$f_i$再不济,也可以继承$g_i$的状态,因为它们状态的定义只与父亲有关。

对于后$50pts$,可以采用背包,设状态$h_j$表示背到了$i$,已经有$j$个单位的能量上传。

由于状态无关子树,即$f_i,g_i$都可以从$h_j$中来。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#define ll long long
#define gc getchar()
using namespace std;
const int M=1e5+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(int x)
{
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int d[M],c[M];
struct edge{int y,next;}a[M<<1];int last[M],len;
void ins(int x,int y){a[++len]=(edge){y,last[x]};last[x]=len;}
namespace task1
{
    const int N=1e5+5;
    int f[N],g[N];//f在父亲之后启动,g是在之前 
    void dfs(int x,int fa)
    {
        g[x]=d[x];int cnt=0;
        for(int k=last[x],y;k;k=a[k].next)
            if((y=a[k].y)!=fa)
            {
                dfs(y,x);
                if(f[y]<g[y])g[x]+=f[y];
                else
                {
                    g[x]+=g[y];
                    if(cnt<d[x]&&c[y])
                    {
                        --g[x];++cnt;
                    }
                }
            }
        f[x]=g[x]-(cnt<d[x]&&c[fa]);
    }
    void solve()
    {
        dfs(1,0);
        qw(g[1]);puts("");
    }
}
namespace task2
{
    const int N=2e3+5;
    int h[N*5],f[N],g[N];
    void dfs(int x,int fa)
    {
        for(int k=last[x],y;k;k=a[k].next)
            if((y=a[k].y)!=fa)dfs(y,x);
        h[0]=0;int siz=0;
        for(int k=last[x],y;k;k=a[k].next)
            if((y=a[k].y)!=fa)
            {
                for(int j=siz+1;j<=siz+c[y];j++)h[j]=1e9;
                siz+=c[y];
                for(int j=siz;j>=0;j--)
                    if(j>=c[y])h[j]=min(h[j-c[y]]+g[y],h[j]+f[y]);
                    else h[j]=h[j]+f[y];
            }
        f[x]=g[x]=1e9;
        for(int j=siz;j>=0;j--)
            g[x]=min(g[x],h[j]+max(d[x]-j,0)),
            f[x]=min(f[x],h[j]+max(d[x]-j-c[fa],0));
    }
    void solve()
    {
        dfs(1,0);
        qw(min(f[1],g[1]));puts("");
    }
}
int main()
{
    int n,mx=0;qr(n);
    for(int i=1;i<=n;i++)qr(d[i]);
    for(int i=1;i<=n;i++)qr(c[i]),mx=max(c[i],mx);
    for(int i=1,x,y;i<n;i++)qr(x),qr(y),ins(x,y),ins(y,x);
    if(mx<=1)task1::solve();
    else task2::solve();
    return 0;
}