#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define FF first
#define SS second
#define all(a) a.begin(), a.end()
#define mod (ll)(1000000007)
int n, m, k;
vector<int>P, Order;
vector<array<int, 2>>Q;
vector<vector<int>>A;
vector<map<int, int>>dp;
void pre(){
P.clear(), Order.clear(), Q.clear(), A.clear(), dp.clear();
P.resize(n+1), Q.resize(n+1), A.resize(n+1), dp.resize(n+1);
}
void dfs(int u){
for(int i=0;i<A[u].size();i++){
int v=A[u][i];
if(v!=P[u])
dfs(v);
}
Order.push_back(u);
}
signed main(){
ios_base::sync_with_stdio(0);cin.tie(0);
cin>>n>>m>>k;
pre();
for(int i=2;i<=n;i++){
cin>>P[i];
int u=i, v=P[i];
A[u].push_back(v);
A[v].push_back(u);
}
for(int j=0;j<m;j++){
int v, d, c;
cin>>v>>d>>c;
Q[v]={d, c};
}
dfs(1);
for(int kk=0;kk<n;kk++){
int u=Order[kk], mx=0;
for(auto v:A[u]){
if(v==P[u])
continue;
if(dp[v].size()>dp[mx].size())
mx=v;
}
if(mx)
swap(dp[u], dp[mx]);
for(auto v:A[u]){
if(v==P[u] || v==mx)
continue;
for(auto it:dp[v]){
int d=it.FF, benf=it.SS;
dp[u][d]+=benf;
}
}
int d=Q[u][0], benf=Q[u][1];
if(d){
dp[u][d]+=benf;
auto it=dp[u].upper_bound(d);
int mx_x=0, pre=0;
for(;it!=dp[u].end();it++){
pre+=it->SS;
if(benf<pre)
break;
mx_x=it->FF;
}
while(true){
it=dp[u].upper_bound(d);
if(it==dp[u].end())
break;
if(it->FF>mx_x){
it->SS-=benf;
break;
}
dp[u].erase(it);
}
}
}
int ans=0;
for(auto it:dp[1]){
ans+=it.SS;
}
cout<<ans;
}
Compilation message
magictree.cpp: In function 'void dfs(long long int)':
magictree.cpp:21:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for(int i=0;i<A[u].size();i++){
| ~^~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
63 ms |
22976 KB |
Output is correct |
2 |
Correct |
41 ms |
19692 KB |
Output is correct |
3 |
Correct |
122 ms |
41368 KB |
Output is correct |
4 |
Correct |
61 ms |
25820 KB |
Output is correct |
5 |
Correct |
97 ms |
26872 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
468 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
65 ms |
19956 KB |
Output is correct |
2 |
Correct |
69 ms |
19344 KB |
Output is correct |
3 |
Correct |
45 ms |
18976 KB |
Output is correct |
4 |
Correct |
41 ms |
21700 KB |
Output is correct |
5 |
Correct |
39 ms |
20736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
3416 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |