#define taskname "BIOCHIP"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5+10;
const int maxk = 2e5 + 1;
struct iii {int ff, ss, tt;};
vector<int> adj[maxn];
int v[maxn], in[maxn], out[maxn], n, m, root, tme;
vector<int> bit[2];
iii qr[maxn];
int dp[maxk][501];
//dp[i][j]: choose j from the first i
void upd(int pos, int val, int id) {for (; pos<=2*n; pos+=(pos&-pos)) bit[id][pos] = max(bit[id][pos], val);}
int qry(int pos, int id) {int ans = 0; for (; pos; pos-=(pos&-pos)) ans = max(ans, bit[id][pos]); return ans;}
bool cmp(iii x, iii y) {return x.ss < y.ss;}
void DFS(int u)
{
in[u] = ++tme;
for (int v: adj[u]) DFS(v);
out[u] = ++tme;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
//freopen(taskname".inp", "r", stdin);
//freopen(taskname".out", "w", stdout);
cin>>n>>m;
for (int i=1, x; i<=n; i++)
{
cin>>x>>v[i];
if (!x) root = i;
else adj[x].emplace_back(i);
}
bit[0].resize(n<<1|1);
bit[1].resize(n<<1|1);
DFS(root);
for (int i=1; i<=n; i++) qr[i] = {in[i], out[i], v[i]};
sort(qr+1, qr+n+1, cmp);
for (int i=1; i<=m; i++)
{
for (int j=i; j<=n; j++)
{
int tmp = qry(qr[i].ff, 0);
upd(qr[i].ss, tmp + qr[i].tt, 1);
}
swap(bit[0], bit[1]);
bit[1].clear();
}
cout<<qry(n<<1, 0);
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
7 ms |
9676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
