1 #include <bits/stdc++.h> 2 using namespace std; 3 #define rg register 4 #define ll long long 5 #define ld long double 6 #define FOR(i,a,b) for(register int i=a;i<=b;++i) 7 #define For(i,a,b) for(register int i=a;i>=b;--i) 8 static char buf[100000],*pa(buf),*pb(buf); 9 inline int rd();inline void wrt(int x);inline ll rdll();inline void wrtll(ll x); 10 #define gc getchar() 11 const ll INF=1E+17,modd=998244353,N=2E+3+10; 12 13 int T,n,fa[N],mx1[N]; 14 ll a[N],t[N],f[N][N][2],bagg[N],bg[N][2],ans; 15 vector<int> chd[N],cd[N]; 16 bool vis[N],vis1[N]; 17 18 void ps(int u) 19 { 20 vis1[u]=1; 21 FOR(i,0,int(cd[u].size())-1) 22 { 23 int v=cd[u][i]; 24 if(vis1[v]) 25 { 26 chd[v].push_back(u); 27 fa[u]=v; 28 } 29 else ps(v); 30 } 31 } 32 33 void doo(int u) 34 { 35 vis[u]=1; 36 if(chd[u].size()==0) 37 { 38 f[u][0][1]=0; 39 f[u][0][0]=a[u]; 40 f[u][1][0]=0; 41 mx1[u]=1;return; 42 } 43 FOR(i,0,int(chd[u].size())-1) 44 { 45 int v=chd[u][i]; 46 if(!vis[v]) doo(v); 47 mx1[u]+=mx1[v]; 48 } 49 //bb1 50 memset(bagg,3,sizeof(bagg));bagg[0]=0; 51 FOR(i,0,int(chd[u].size())-1) For(j,mx1[u],0) 52 { 53 bagg[j]=bagg[j]+f[chd[u][i]][0][0]; 54 FOR(k,1,j) 55 bagg[j]=min(bagg[j],bagg[j-k]+f[chd[u][i]][k][0]); 56 } 57 FOR(i,0,mx1[u]) f[u][i][0]=min(f[u][i][0],bagg[i]); 58 //bb2 59 memset(bagg,3,sizeof(bagg));bagg[0]=0; 60 FOR(i,0,int(chd[u].size())-1) For(j,mx1[u],0) 61 { 62 bagg[j]=bagg[j]+min(f[chd[u][i]][0][0],f[chd[u][i]][0][1]); 63 FOR(k,1,j) 64 bagg[j]=min(bagg[j],bagg[j-k]+min(f[chd[u][i]][k][0],f[chd[u][i]][k][1])); 65 } 66 FOR(i,0,mx1[u]) f[u][i][0]=min(f[u][i][0],bagg[i]+a[u]); 67 //bb3 68 memset(bg,3,sizeof(bg));bg[0][0]=0; 69 FOR(i,0,int(chd[u].size())-1) For(j,mx1[u],0) 70 { 71 bg[j][1]=min(bg[j][1]+f[chd[u][i]][0][0],bg[j][0]+f[chd[u][i]][0][1]); 72 bg[j][0]=bg[j][0]+f[chd[u][i]][0][0]; 73 FOR(k,1,j) 74 bg[j][1]=min(bg[j][1],bg[j-k][0]+f[chd[u][i]][k][1]), 75 bg[j][1]=min(bg[j][1],bg[j-k][1]+f[chd[u][i]][k][0]), 76 bg[j][0]=min(bg[j][0],bg[j-k][0]+f[chd[u][i]][k][0]); 77 } 78 FOR(i,0,mx1[u]) f[u][i][1]=min(f[u][i][1],min(bg[i][0],bg[i][1])); 79 return; 80 } 81 82 int main() 83 { 84 T=rd();while(T--){ 85 memset(f,3,sizeof(f)); 86 ans=INF; 87 memset(mx1,0,sizeof(mx1)); 88 memset(vis,0,sizeof(vis)); 89 memset(vis1,0,sizeof(vis1)); 90 //f0 91 n=rd(); 92 FOR(i,1,n) chd[i].clear(),cd[i].clear(); 93 //FOR(i,1,n) cout<<chd[i].size()<<" ";cout<<endl; 94 FOR(i,1,n) a[i]=rdll(); 95 FOR(i,1,n) t[i]=rdll(); 96 FOR(i,1,n-1) 97 { 98 int u=rd(),v=rd(); 99 cd[u].push_back(v); 100 cd[v].push_back(u); 101 } 102 ps(1); 103 doo(1); 104 FOR(i,0,mx1[1]) ans=min(ans,t[i]+min(f[1][i][0],f[1][i][1])); 105 cout<<ans<<endl; 106 }return 0; 107 } 108 inline int rd() 109 { 110 register int x(0);register char c(gc);bool bbb=1; 111 if(c=='-') {bbb=0;c=gc;} 112 while(c<'0'||c>'9')c=gc; 113 while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc; 114 if(bbb)return x;else return -x; 115 } 116 inline ll rdll() 117 { 118 register ll x(0);register char c(gc);bool bbb=1; 119 if(c=='-') {bbb=0;c=gc;} 120 while(c<'0'||c>'9')c=gc; 121 while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc; 122 if(bbb)return x;else return -x; 123 }
标签:bg,chd,Her,Lost,min,int,CCPC,mx1,bagg From: https://www.cnblogs.com/universeplayer/p/16889967.html