1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
|
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
namespace mine
{
typedef long long ll;
const int INF=0x3f3f3f3f;
const int MAX_N=2100;
int hou[MAX_N],siz[MAX_N];
struct Edge{int y,g;}e[MAX_N*2];
int ln=0;void (int x,int y) {e[++ln]=(Edge){y,hou[x]};hou[x]=ln;}
int f[2][MAX_N][MAX_N],ned[MAX_N];
void chmax(int &x,int y) {x=max(x,y);}
void dp(int x,int fa)
{
int now=0;siz[x]=1;
for(int k=hou[x];k>0;k=e[k].g)
{
int y=e[k].y;if(y==fa) continue;
dp(y,x);
for(int a=0;a<=siz[x];a++)
for(int b=0;b<=siz[y];b++)
{
int up=f[0][y][b];if(up==f[0][0][0]) continue;
chmax(f[now^1][x][a+b+1],f[now][x][a]+up-ned[y]);
if(up>=ned[y]) chmax(f[now^1][x][a+b],f[now][x][a]);
}
siz[x]+=siz[y];
memset(f[now][x],-63,sizeof f[now][x]);now^=1;
}
memcpy(f[0][x],f[now][x],sizeof f[0][x]);
}
void main()
{
memset(f,-63,sizeof f);
int n,st;scanf("%d%d",&n,&st);
for(int i=1;i<=n;i++) f[0][i][0]=st,scanf("%d",&ned[i]);
for(int i=1;i<n;i++)
{
int x,y;scanf("%d%d",&x,&y);
ins(x,y);ins(y,x);
}
dp(1,0);
int ans=-1;for(int i=n;i>=0;i--) if(f[0][1][i]>=ned[1]) ans=i;
printf("%d",ans);
}
};
int main()
{
srand(time(0));
mine::main();
}
|
近期评论