이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define ff first
#define ss second
vector<int> q[300100];
ll a[300100];
ll dp[300100][2];
ll kto[300100];
int us[300100];
void dfs(int v, int p){
dp[v][0] = a[v];
dp[v][1] = 0;
for(int to: q[v]){
if(to == p) continue;
dfs(to, v);
dp[v][0] += dp[to][0];
dp[v][1] += dp[to][1];
}
if(dp[v][1] > dp[v][0]) kto[v] = 0;
else kto[v] = 1;
dp[v][1] = min(dp[v][1], dp[v][0]);
}
void dfs2(int v, int p, int k){
if(k == 1){
k = kto[v];
}
us[v] = k;
for(int to: q[v]){
if(to == p) continue;
dfs2(to, v, k);
}
}
void solve(){
ll n, s;
cin>>n>>s;
ll ans = s;
for(int i=1; i<=n; i++){
int l, r;
cin>>l>>r;
q[r].pb(i);
q[i].pb(r);
a[i] = l;
ans += a[i];
}
dfs(0, -1);
dfs2(0, -1, 1);
ans = 0;
for(int i=0; i<=n; i++){
ans += a[i] * us[i];
}
cout<<ans;
}
signed main(){
solve();
}
# | 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... |