一道题变两道题。。。
由于父亲会影响到儿子,那么就要分情况讨论了。
对于前$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;
}
最后一次更新于2020-07-16
0 条评论