#include <bits/stdc++.h>
#define N 100005
#define ll long long int
#define fo(i,x,y) for(int i=x;i<=y;i++)
#define fs(ar,n) fo(i,1,n) cin>>ar[i]
#define sp " "
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define mod 1000000007
using namespace std;
ll n,m,ar[N],sum,t,k,dp[1005][1005],val[N],dad[N];
vector<int> v[N];
// vector<int> v2[N];
// ll f(int ind,int back,int l)
// {
// if(dp[ind][l]!=-1)
// return dp[ind][l];
// ll t1=0;
// ll t2=0;
// for(int i=0;i<v[ind].size();i++)
// t1+=f(v[ind][i],ind,l);
// if(ar[ind]<ar[l] && ar[ind]!=0)
// for(int i=0;i<v[ind].size();i++)
// t2+=f(v[ind][i],ind,ind);
// if(ar[ind]<ar[l] && ar[ind]!=0)
// t2+=val[ind];
// if(ar[ind]==ar[l] && ar[l]!=0)
// t1+=val[ind];
// // cout<<ind<<sp<<l<<sp<<t1<<sp<<t2<<endl;
// return dp[ind][l]=max(t1,t2);
// }
ll f(int ind,int back,int l)
{
if(dp[ind][l]!=-1)
return dp[ind][l];
ll t1=0;
ll t2=0;
for(int i=0;i<v[ind].size();i++)
t1+=f(v[ind][i],ind,l);
if(ar[ind]<l && ar[ind]!=0)
for(int i=0;i<v[ind].size();i++)
t2+=f(v[ind][i],ind,ar[ind]);
if(ar[ind]<l && ar[ind]!=0)
t2+=val[ind];
if(ar[ind]==l && l!=0)
t1+=val[ind];
// cout<<ind<<sp<<l<<sp<<t1<<sp<<t2<<endl;
return dp[ind][l]=max(t1,t2);
}
int main()
{
fast;
cin>>n>>m>>k;
memset(dp,-1,sizeof(dp));
fo(i,2,n)
{
int a;
cin>>a;
// v2[a].pb(i);
dad[i]=a;
}
fo(i,1,m)
{
ll a,b,c;
cin>>a>>b>>c;
ar[a]=b;
val[a]=c;
}
dad[1]=1;
ar[0]=1e7;
fo(i,2,n)
if(ar[i])
{
v[dad[dad[i]]].pb(i);
dad[i]=i;
}
cout<<f(1,1,1e7);
// fo(i,1,n)
// sum+=val[i];
// cout<<sum<<endl;
// cout<<endl;
// fo(i,1,n)
// cout<<val[i]<<sp;
// cout<<endl;
}
Compilation message
magictree.cpp: In function 'long long int f(int, int, int)':
magictree.cpp:47:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | for(int i=0;i<v[ind].size();i++)
| ~^~~~~~~~~~~~~~
magictree.cpp:50:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=0;i<v[ind].size();i++)
| ~^~~~~~~~~~~~~~
magictree.cpp: In function 'int main()':
magictree.cpp:43:14: warning: array subscript 10000000 is above array bounds of 'long long int [1005]' [-Warray-bounds]
43 | if(dp[ind][l]!=-1)
| ~~~~~~~~~^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
21248 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
45 ms |
26872 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
21376 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
71 ms |
28920 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
21248 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
24 ms |
22272 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
21248 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
25 ms |
21248 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
