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>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
vector<pair<int,int>> adj[300000];
int W[300000], C[300000];
long long A[300000], B[300000];
priority_queue<long long> Q[300000];
int prep(int c)
{
W[C[c]=c]=1;
for(auto &n: adj[c]) {
W[c]+=prep(n.first);
if(W[adj[c][0].first]<W[n.first]) swap(adj[c][0],n);
}
if(adj[c].size()) C[c]=C[adj[c][0].first];
return W[c];
}
void solve(int c)
{
long long t1, t2;
if(C[c]==c) {
Q[c].push(0); Q[c].push(0); A[c]=1;
return;
}
for(auto[n,w]: adj[c]) {
solve(n);
t1=Q[C[n]].top(); Q[C[n]].pop();
t2=Q[C[n]].top(); Q[C[n]].pop();
Q[C[n]].push(t1+w); Q[C[n]].push(t2+w); B[C[n]]+=w;
if(C[c]^C[n]) {
A[C[c]]+=A[C[n]];
B[C[c]]+=B[C[n]];
while(!Q[C[n]].empty()) {
Q[C[c]].push(Q[C[n]].top());
Q[C[n]].pop();
}
}
}
while(Q[C[c]].size()>A[C[c]]+1) Q[C[c]].pop();
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int N, M;
stack<long long> res;
long long ans, x=0;
cin>>N>>M; N+=M; M=1;
for(int i=1;i<N;i++) {
int p, c;
cin>>p>>c;
adj[--p].emplace_back(i,c);
}
prep(0); solve(0); ans=B[C[0]];
while(Q[C[0]].size()) {
res.push(Q[C[0]].top());
Q[C[0]].pop(); M--;
}
while(res.size()) {
ans+=(res.top()-x)*M++;
x=res.top();
res.pop();
}
cout<<ans<<'\n';
return 0;
}
Compilation message (stderr)
fireworks.cpp: In function 'void solve(int)':
fireworks.cpp:50:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(Q[C[c]].size()>A[C[c]]+1) Q[C[c]].pop();
~~~~~~~~~~~~~~^~~~~~~~~~
# | 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... |