Description
给定一棵 (n) 个节点的有根树，每个点有一个权值 (val_i) 。你需要选择尽可能多的节点，使得：对于任意两个点 (i,j) ，如果 (i) 在树上是 (j) 的祖先，那么 (v_i>v_j) 。请计算可选的最多的点数，注意这些点不必形成这棵树的一个连通子树。
(1leq nleq 200000)
Solution
记 (f_{u,i}) 表示在 (u) 节点的子树中选取的最大的点权为 (i) 的方案最大值。
那么转移就是枚举其子树中的状态，并在其它的子树中找到点权小于等于其的最大的方案值。
这样是 (O(n^2)) 的，考虑优化更新过程。
容易发现，转移时就是用一个前缀最大值更新一个后缀，用线段树维护，合并节点信息时启发式合并即可。
复杂度为 (O(nlog^2 n)) 的。
Code
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 200000, inf = ~0u>>1;
int n, val[N+5], f, b[N+5], tot, size[N+5], s[N+5][3], top;
vector<int>to[N+5];
struct Segment_tree {
int root[N+5], ch[N*50+5][2], maxn[N*50+5], tag[N*50+5], pos;
void pushdown(int o) {
tag[ch[o][0]] += tag[o], tag[ch[o][1]] += tag[o];
maxn[ch[o][0]] += tag[o], maxn[ch[o][1]] += tag[o];
tag[o] = 0;
}
void get(int o, int l, int r) {
if (!o) return;
if (l == r) {s[++top][0] = l, s[top][1] = maxn[o]; return; }
if (tag[o]) pushdown(o); int mid = (l+r)>>1;
get(ch[o][0], l, mid); get(ch[o][1], mid+1, r);
}
void update(int &o, int l, int r, int loc, int val) {
if (!o) o = ++pos; maxn[o] = max(maxn[o], val);
if (l == r) return;
if (tag[o]) pushdown(o); int mid = (l+r)>>1;
if (loc <= mid) update(ch[o][0], l, mid, loc, val);
else update(ch[o][1], mid+1, r, loc, val);
}
void modify(int o, int l, int r, int a, int b, int val) {
if (!o || a > b) return;
if (a <= l && r <= b) {tag[o] += val, maxn[o] += val; return; }
if (tag[o]) pushdown(o); int mid = (l+r)>>1;
if (a <= mid) modify(ch[o][0], l, mid, a, b, val);
if (b > mid) modify(ch[o][1], mid+1, r, a, b, val);
maxn[o] = 0;
if (ch[o][0]) maxn[o] = max(maxn[ch[o][0]], maxn[o]);
if (ch[o][1]) maxn[o] = max(maxn[ch[o][1]], maxn[o]);
}
int query(int o, int l, int r, int a, int b) {
if (!o || a > b) return 0;
if (a <= l && r <= b) return maxn[o];
if (tag[o]) pushdown(o); int mid = (l+r)>>1, c1 = 0, c2 = 0;
if (a <= mid) c1 = query(ch[o][0], l, mid, a, b);
if (b > mid) c2 = query(ch[o][1], mid+1, r, a, b);
return max(c1, c2);
}
}T;
void dfs(int u) {
for (int i = 0, sz = to[u].size(), v; i < sz; i++) {
dfs(v = to[u][i]);
if (size[u] == 0) T.root[u] = T.root[v];
else {
int a = u, b = v;
if (size[a] > size[b]) swap(a, b);
top = 0; T.get(T.root[a], 1, tot);
for (int j = 1; j <= top; j++) {
s[j][2] = max(s[j-1][2], s[j][1]);
s[j][1] += T.query(T.root[b], 1, tot, 1, s[j][0]);
}
for (int j = 1; j <= top; j++) T.modify(T.root[b], 1, tot, s[j][0]+1, (j == top ? tot : s[j+1][0]), s[j][2]);
for (int j = 1; j <= top; j++) T.update(T.root[b], 1, tot, s[j][0], s[j][1]);
T.root[u] = T.root[b];
}
size[u] += size[v];
}
++size[u];
T.update(T.root[u], 1, tot, val[u], T.query(T.root[u], 1, tot, 1, val[u]-1)+1);
}
void work() {
scanf("%d", &n); b[++tot] = val[0] = inf;
for (int i = 1; i <= n; i++) {
scanf("%d%d", &val[i], &f);
to[f].pb(i); b[++tot] = val[i];
}
sort(b+1, b+tot+1); tot = unique(b+1, b+tot+1)-b-1;
for (int i = 0; i <= n; i++) val[i] = lower_bound(b+1, b+tot+1, val[i])-b;
dfs(0); printf("%d
", T.query(T.root[0], 1, tot, tot, tot)-1);
}
int main() {work(); return 0; }