#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=pre-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 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
324 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
320 KB |
Output is correct |
7 |
Correct |
1 ms |
316 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
312 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
21884 KB |
Output is correct |
2 |
Correct |
36 ms |
18748 KB |
Output is correct |
3 |
Correct |
117 ms |
38944 KB |
Output is correct |
4 |
Correct |
61 ms |
23760 KB |
Output is correct |
5 |
Correct |
90 ms |
24516 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
44 ms |
20572 KB |
Output is correct |
5 |
Correct |
68 ms |
24152 KB |
Output is correct |
6 |
Correct |
61 ms |
20596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
57 ms |
17856 KB |
Output is correct |
2 |
Correct |
59 ms |
17088 KB |
Output is correct |
3 |
Correct |
45 ms |
16780 KB |
Output is correct |
4 |
Correct |
39 ms |
19944 KB |
Output is correct |
5 |
Correct |
38 ms |
18628 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
324 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
320 KB |
Output is correct |
7 |
Correct |
1 ms |
316 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
312 KB |
Output is correct |
10 |
Correct |
64 ms |
22040 KB |
Output is correct |
11 |
Correct |
72 ms |
21048 KB |
Output is correct |
12 |
Correct |
46 ms |
18260 KB |
Output is correct |
13 |
Correct |
38 ms |
21192 KB |
Output is correct |
14 |
Correct |
39 ms |
20124 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
3284 KB |
Output is correct |
2 |
Correct |
31 ms |
15096 KB |
Output is correct |
3 |
Correct |
31 ms |
15160 KB |
Output is correct |
4 |
Correct |
41 ms |
15168 KB |
Output is correct |
5 |
Correct |
16 ms |
15352 KB |
Output is correct |
6 |
Correct |
27 ms |
16208 KB |
Output is correct |
7 |
Correct |
24 ms |
16656 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
324 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
320 KB |
Output is correct |
7 |
Correct |
1 ms |
316 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
312 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
468 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
44 ms |
20572 KB |
Output is correct |
14 |
Correct |
68 ms |
24152 KB |
Output is correct |
15 |
Correct |
61 ms |
20596 KB |
Output is correct |
16 |
Correct |
64 ms |
22040 KB |
Output is correct |
17 |
Correct |
72 ms |
21048 KB |
Output is correct |
18 |
Correct |
46 ms |
18260 KB |
Output is correct |
19 |
Correct |
38 ms |
21192 KB |
Output is correct |
20 |
Correct |
39 ms |
20124 KB |
Output is correct |
21 |
Correct |
14 ms |
5960 KB |
Output is correct |
22 |
Correct |
72 ms |
22964 KB |
Output is correct |
23 |
Correct |
77 ms |
26304 KB |
Output is correct |
24 |
Correct |
110 ms |
34452 KB |
Output is correct |
25 |
Correct |
68 ms |
25160 KB |
Output is correct |
26 |
Correct |
85 ms |
24424 KB |
Output is correct |
27 |
Correct |
69 ms |
20216 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
324 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
0 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
320 KB |
Output is correct |
7 |
Correct |
1 ms |
316 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
312 KB |
Output is correct |
10 |
Correct |
57 ms |
21884 KB |
Output is correct |
11 |
Correct |
36 ms |
18748 KB |
Output is correct |
12 |
Correct |
117 ms |
38944 KB |
Output is correct |
13 |
Correct |
61 ms |
23760 KB |
Output is correct |
14 |
Correct |
90 ms |
24516 KB |
Output is correct |
15 |
Correct |
1 ms |
468 KB |
Output is correct |
16 |
Correct |
1 ms |
468 KB |
Output is correct |
17 |
Correct |
1 ms |
468 KB |
Output is correct |
18 |
Correct |
44 ms |
20572 KB |
Output is correct |
19 |
Correct |
68 ms |
24152 KB |
Output is correct |
20 |
Correct |
61 ms |
20596 KB |
Output is correct |
21 |
Correct |
57 ms |
17856 KB |
Output is correct |
22 |
Correct |
59 ms |
17088 KB |
Output is correct |
23 |
Correct |
45 ms |
16780 KB |
Output is correct |
24 |
Correct |
39 ms |
19944 KB |
Output is correct |
25 |
Correct |
38 ms |
18628 KB |
Output is correct |
26 |
Correct |
64 ms |
22040 KB |
Output is correct |
27 |
Correct |
72 ms |
21048 KB |
Output is correct |
28 |
Correct |
46 ms |
18260 KB |
Output is correct |
29 |
Correct |
38 ms |
21192 KB |
Output is correct |
30 |
Correct |
39 ms |
20124 KB |
Output is correct |
31 |
Correct |
5 ms |
3284 KB |
Output is correct |
32 |
Correct |
31 ms |
15096 KB |
Output is correct |
33 |
Correct |
31 ms |
15160 KB |
Output is correct |
34 |
Correct |
41 ms |
15168 KB |
Output is correct |
35 |
Correct |
16 ms |
15352 KB |
Output is correct |
36 |
Correct |
27 ms |
16208 KB |
Output is correct |
37 |
Correct |
24 ms |
16656 KB |
Output is correct |
38 |
Correct |
14 ms |
5960 KB |
Output is correct |
39 |
Correct |
72 ms |
22964 KB |
Output is correct |
40 |
Correct |
77 ms |
26304 KB |
Output is correct |
41 |
Correct |
110 ms |
34452 KB |
Output is correct |
42 |
Correct |
68 ms |
25160 KB |
Output is correct |
43 |
Correct |
85 ms |
24424 KB |
Output is correct |
44 |
Correct |
69 ms |
20216 KB |
Output is correct |
45 |
Correct |
16 ms |
6380 KB |
Output is correct |
46 |
Correct |
68 ms |
24088 KB |
Output is correct |
47 |
Correct |
85 ms |
27456 KB |
Output is correct |
48 |
Correct |
124 ms |
37524 KB |
Output is correct |
49 |
Correct |
61 ms |
25788 KB |
Output is correct |
50 |
Correct |
89 ms |
25308 KB |
Output is correct |
51 |
Correct |
91 ms |
21016 KB |
Output is correct |