#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int base = 31;
const int NMAX = 200002;
const int INF = 1e9;
const int VMAX = 501;
const int nrbits = 17;
const int MOD = 1000000007;
int dp[NMAX][VMAX];
vector <int> g[NMAX];
int timp[NMAX];
int stamp;
int v[NMAX];
int m;
int root;
void maxSelf(int &x, int val){
x = max(x, val);
}
void DFS(int node, int p){
timp[node] = stamp;
for(auto x : g[node]){
if(x == p) continue;
DFS(x, node);
}
++stamp;
for(int i = 0; i <= m; i++){
dp[stamp][i] = dp[stamp - 1][i];
}
for(int i = 1; i <= m; i++){
maxSelf(dp[stamp][i], dp[timp[node]][i - 1] + v[node]);
}
}
int main() {
ifstream cin("d.in");
ofstream cout("d.out");
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n >> m;
for(int i = 0; i <= m; i++)
dp[0][i] = -INF;
dp[0][0] = 0;
for(int i = 1; i <= n; i++){
int p;
cin >> p >> v[i];
if(p == 0){
root = i;
}else{
g[i].push_back(p);
g[p].push_back(i);
}
}
DFS(root, 0);
cout << dp[stamp][m];
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 2 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 4 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 5 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 6 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 7 |
Incorrect |
2 ms |
4948 KB |
Output isn't correct |
| 8 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
| 9 |
Incorrect |
4 ms |
4948 KB |
Output isn't correct |
| 10 |
Incorrect |
3 ms |
4948 KB |
Output isn't correct |
