#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define fr first
#define sc second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(),x.end()
#define sp << " " <<
#define inf 1e15
#define N 5000
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef tuple<int,int,int> tiii;
typedef pair<int,int> pii;
int n,a[N+5],f[N+5],d[N+5][N+5];
vector<int> g[N+5];
int dfs(int x,int ata){
for(int i=a[x]+1;i<=n;i++)
d[x][i]=f[i];
for(auto c:g[x]){
if(c==ata) continue;
int t=dfs(c,x);
if(a[x]+1==a[c]){
for(int i=a[x]+2;i<=n;i++)
d[x][i]+=d[c][i]-f[i];
d[x][a[x]+1]+=t;
}
else if(a[c]==0){
for(int i=a[x]+2;i<=n;i++)
d[x][i]+=t;
d[x][a[x]+1]+=d[c][a[x]+1]-f[a[x]+1];
}
else{
for(int i=a[x]+1;i<=n;i++)
d[x][i]+=t;
}
}
int ans=inf;
for(int i=a[x]+1;i<=n;i++)
ans=min(ans,d[x][i]);
return ans;
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin >> n;
for(int i=1;i<=n;i++) cin >> a[i];
for(int i=1;i<=n;i++) cin >> f[i];
for(int i=1;i<n;i++){
int x,y;
cin >> x >> y;
g[x].pb(y);
g[y].pb(x);
}
cout << dfs(1,0) << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |