#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<long long, long long> pll;
typedef pair<int,int> pii;
typedef vector<long long> vl;
typedef vector<int> vi;
int n, m;
vector<pair<int, ll> > G[300100];
vector<pll> active[300100];
void dfs(int node, int p){
// cout<<node<<endl;
// vi children;
for(auto next : G[node]){
if(next.first != p){
dfs(next.first, node);
for(auto t : active[next.first]){
active[node].pb(mp(t.first + next.second, t.second));
}
}
}
if(active[node].size() == 0){
active[node].pb(mp(0, 0));
return;
}
// cout<<node<<" "<<active[node].size()<<endl;
sort(active[node].begin(), active[node].end());
ll eden = 0, dva = 0;
int mid = ((int)active[node].size()-1)/2;
// cout<<"Choosed AT: "<<node<<" "<<active[node][mid].first<<" "<<active[node][mid].second<<endl;
ll wei1 = active[node][mid].first, wei2 = 0;
for(auto t : active[node]){
eden += t.second + abs(t.first - wei1);
// cout<<"FROM "<<t.first<<" to "<<wei1<<endl;
}
// cout<<"ONLY USED: "<<eden<<endl;
mid++;
if(active[node].size()%2 == 0){
wei2 = active[node][mid].first;
for(auto t : active[node]){
dva += t.second + abs(t.first - active[node][mid].first);
}
}
active[node].clear();
// active[node].pb(mp(wei1, eden));
if(dva != 0 && wei2 != 0){
if(eden > dva)
active[node].pb(mp(wei2, dva));
else
active[node].pb(mp(wei1, eden));
}
else
active[node].pb(mp(wei1, eden));
}
int main(){
cin>>n>>m;
vector<array<int, 3>> edge;
for(int i = 1; i < n + m; i++){
int a, b;
cin>>a>>b;
a--;
edge.pb({i, a, b});
G[a].pb(mp(i, b));
G[i].pb(mp(a, b));
}
// cout<<endl;
dfs(0, -1);
ll ans = 1e9;
for(auto t : active[0]){
ans = min(ans, t.second);
}
cout<<ans<<endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
14292 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
14292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
14292 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
7 ms |
14292 KB |
Output is correct |
| 2 |
Incorrect |
7 ms |
14292 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
