题意
给定一颗 (N) 个点的有根树,编号一次为 (1) 到 (N),其中 (1) 号点为根节点。每个节点有一个权值 (v)
你可以修改任意个点的点权,使这颗树满足下面的性质:
对于任意两点 (i,j),如果 (i) 在树上是 (j) 的祖先,那么 (v_i<=v_j)
请你最小化修改的次数
解法
考虑一条链的情况,我们把从叶子到根的数提取出来,可以发现实际上就是对这一序列求一个最长不上升子序列:因为要求修改的数最少实际上是要求保留的数最多
这个结论实际上是可以推广到树上的:考虑一个节点 (x),在到达 (x) 之前其子树的答案实际上是互不影响的,那么在计算 (x) 的贡献时我们把子树合并即可
维护 (LIS) 用经典的 (O(n log n)) 的单调栈方法即可,为了方便合并,可以用 multiset 替代单调栈来维护。合并时可以启发式合并保证复杂度
代码
#include <iostream>
#include <cstdio>
#include <set>
using namespace std;
const int MAX_N = 2e5 + 10;
int N;
int a[MAX_N];
int head[MAX_N], to[MAX_N << 1], nxt[MAX_N << 1], cap;
inline void link(int u, int v) { to[++cap] = v, nxt[cap] = head[u], head[u] = cap; }
multiset<int> s[MAX_N];
typedef multiset<int>::iterator iter;
void DFS(int x, int fa) {
for (int i = head[x]; i; i = nxt[i]) {
int v = to[i];
if (v ^ fa) {
DFS(v, x);
if (s[x].size() < s[v].size()) swap(s[x], s[v]);
for (iter it = s[v].begin(); it != s[v].end(); ++it) s[x].insert(*it);
}
}
iter it = s[x].lower_bound(a[x]);
if (it != s[x].begin()) s[x].erase(--it);
s[x].insert(a[x]);
}
int main() {
scanf("%d", &N);
for (int i = 1; i <= N; ++i) scanf("%d", a + i);
int u, v;
for (int i = 1; i < N; ++i) {
scanf("%d%d", &u, &v);
link(u, v), link(v, u);
}
DFS(1, 0);
printf("%d
", N - s[1].size());
return 0;
}