#include<bits/stdc++.h>
#define MAXN 300007
using namespace std;
const long long inf=1e17;
int n,m;
int p[MAXN],c[MAXN];
vector< pair<int,long long> > v[MAXN],g[MAXN];
vector<long long> dists;
long long sz[MAXN],ans,dist[MAXN];
void dfs(int x,long long d){
sz[x]=(v[x].empty());
dist[x]=d;
if(sz[x]==1)dists.push_back(d);
for(int i=0;i<v[x].size();i++){
dfs(v[x][i].first,d+v[x][i].second);
sz[x]+=sz[v[x][i].first];
}
}
long long dp[MAXN];
long long sum;
void solve(int x,long long len,long long e){
if(v[x].empty()){
dp[x]=dist[x];
return;
}
long long mins=inf,maxs=-inf;
for(int i=0;i<v[x].size();i++){
solve(v[x][i].first,len,v[x][i].second);
mins=min(mins,v[x][i].second);
maxs=max(maxs,v[x][i].second);
}
dp[x]=dp[v[x][0].first]-v[x][0].second;
for(int i=0;i<v[x].size();i++){
v[x][i].second=min(maxs,max(mins,len-dp[v[x][i].first]+v[x][i].second));
}
dp[x]=dp[x]+v[x][0].second;
}
void poss(int x,long long add){
for(int i=0;i<v[x].size();i++){
v[x][i].second+=add;
if(v[x][i].second<0){
poss(v[x][i].first,-v[x][i].second);
v[x][i].second=0;
}else{
poss(v[x][i].first,0);
}
}
for(int i=0;i<v[x].size();i++){
sum+=abs(v[x][i].second-g[x][i].second);
}
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n>>m;
n+=m;
for(int i=2;i<=n;i++){
cin>>p[i]>>c[i];
v[p[i]].push_back({i,c[i]});
g[p[i]].push_back({i,c[i]});
}
dfs(1,0);
ans=inf;
for(long long len=1;len<=300;len++){
for(int i=1;i<=n;i++)v[i]=g[i];
sum=0;
solve(1,len,0);
poss(1,0);
ans=min(ans,sum);
}
cout<<ans<<"\n";
return 0;
}
Compilation message
fireworks.cpp: In function 'void dfs(int, long long int)':
fireworks.cpp:20:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
20 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
fireworks.cpp: In function 'void solve(int, long long int, long long int)':
fireworks.cpp:37:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
fireworks.cpp:46:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
46 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
fireworks.cpp: In function 'void poss(int, long long int)':
fireworks.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
54 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
fireworks.cpp:65:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
65 | for(int i=0;i<v[x].size();i++){
| ~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
14428 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
14424 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
14428 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
14428 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
14428 KB |
Output is correct |
| 2 |
Incorrect |
6 ms |
14428 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
