This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int>adj[1<<18];
int dp[3][1<<18],H[1<<18],T[1<<18];
void dfs(int n,int p){
int sz=0,x=1e12;
dp[0][n]=dp[1][n]=dp[2][n]=1e12;
priority_queue<int>pq;
pq.push(1e12);
for(auto i:adj[n]) if(i-p){
dfs(i,n);sz++;
if(H[i]-H[n])
dp[1+(H[i]<H[n])][i]=1e12;
x+=dp[1][i];
pq.push(dp[1][i]-dp[2][i]);
}
for(int i=0;i<=sz;i++){
x-=pq.top();
pq.pop();
dp[0][n]=min(dp[0][n],x+T[n]*max(i,sz-i));
dp[1][n]=min(dp[1][n],x+T[n]*max(i+1,sz-i));
dp[2][n]=min(dp[2][n],x+T[n]*max(i,sz+1-i));
}
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n;
cin>>n;
for(int i=1;i<=n;i++) cin>>T[i];
for(int i=1;i<=n;i++) cin>>H[i];
for(int i=1,a,b;i<n;i++) cin>>a>>b,
adj[a].push_back(b),adj[b].push_back(a);
dfs(1,0);
cout<<dp[0][1];
}
# | 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... |
# | 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... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |