#include<bits/stdc++.h>
using namespace std;
#define in pair<int, int>
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define INF (int)1e17
const int MX = 2e5+5, SMX = 5e2+2;
#define fast() ios_base::sync_with_stdio(false); cin.tie(NULL)
vector<int> adj[MX];
int dp[MX][SMX];
int chungus[SMX];//initialised with zero.
vector<int> w;
vector<int> euler;
int timer;
vector<int> tin;
int m;
vector<int> tout;
void dfs(int u)
{
euler.pb(u);
tin[u] = timer++;
for(int v: adj[u])
{
dfs(v);
for(int i = 1; i <= m; i++)
chungus[i] = max(chungus[i], dp[tin[v]][i]);
}
for(int i = 1; i <= m; i++)
dp[tin[u]][i] = max(((tin[u] > 0) ? dp[tin[u]-1][i] : 0), w[u] + chungus[i-1]);
return;
}
signed main()
{
fast();
//freopen("d.in", "r", stdin);
//freopen("d.out", "w", stdout);
int n;
cin >> n >> m;
w.resize(n+1);
tin.resize(n+1);
int root = -1;
for(int i = 1; i <= n; i++)
{
int x; cin >> x >> w[i];
if(x)
adj[x].pb(i);
else
root = i;
}
dfs(root);
cout << dp[n-1][m] << "\n";
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
5980 KB |
Output isn't correct |
| 2 |
Correct |
2 ms |
5980 KB |
Output is correct |
| 3 |
Incorrect |
3 ms |
8028 KB |
Output isn't correct |
| 4 |
Incorrect |
11 ms |
23732 KB |
Output isn't correct |
| 5 |
Incorrect |
11 ms |
26972 KB |
Output isn't correct |
| 6 |
Incorrect |
10 ms |
26968 KB |
Output isn't correct |
| 7 |
Incorrect |
278 ms |
298768 KB |
Output isn't correct |
| 8 |
Correct |
258 ms |
298652 KB |
Output is correct |
| 9 |
Correct |
372 ms |
362940 KB |
Output is correct |
| 10 |
Incorrect |
482 ms |
400544 KB |
Output isn't correct |
