Submission #1191308

#TimeUsernameProblemLanguageResultExecution timeMemory
1191308keremNestabilnost (COI23_nestabilnost)C++20
12 / 100
125 ms197076 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...