// Zende bad Shoma nasime faghat !
#include <bits/stdc++.h>
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
using namespace std;
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
const ll Mod = 1000000007LL;
const int N = 2e5 + 10;
const ll Inf = 2242545357980376863LL;
const ll Log = 30;
int n, m;
vector<int> G[N];
int C[N];
priority_queue<ll> pq[N];
void DFS(int u){
if(G[u].empty()){
pq[u].push(C[u]);
pq[u].push(C[u]);
return ;
}
for(auto adj : G[u]){
DFS(adj);
if(pq[adj].size() > pq[u].size())
swap(pq[u], pq[adj]);
while(!pq[adj].empty()){
pq[u].push(pq[adj].top());
pq[adj].pop();
}
}
for(int i = 0; i + 1 < (int) G[u].size(); i++)
pq[u].pop();
ll sn = pq[u].top();
pq[u].pop();
ll s0 = pq[u].top();
pq[u].pop();
pq[u].push(sn + C[u]);
pq[u].push(s0 + C[u]);
//cerr << u << ' ' << pq[u].size() << '\n';
}
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m;
int p;
ll Sum = 0;
for(int i = 2; i <= n + m; i++){
cin >> p >> C[i];
G[p].pb(i);
Sum += C[i];
}
//cerr << "#########\n";
DFS(1);
vector<ll> V;
while(!pq[1].empty()){
V.pb(pq[1].top());
pq[1].pop();
}
//debug
reverse(all(V));
ll M = 1 - ((int) V.size());
//debug(M);
ll po = 0;
while(M < 0){
//cerr << M << ' ' << V[po + 1] - V[po] << '\n';
Sum += M * (V[po + 1] - V[po]);
po ++;
M ++;
}
cout << Sum << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
11264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
11264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
11264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
11264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
