题目描述
小 Y 在学树论时看到了有关二叉树的介绍: 在计算机科学中, 二叉树是每个结点最多有两个子结点的有序树. 通常子结点被称作 “左孩子” 和 “右孩子”. 二叉树被用作二叉搜索 树和二叉堆. 随后他又和他人讨论起了二叉搜索树.
什么是二叉搜索树呢? 二叉搜索树首先是一棵二叉树. 设 key [p] 表示结点 p 上的数值. 对于其中的每个结点 p, 若其存在左孩子 lch, 则 key [p]\(\gt\) key [lch]; 若其存在右孩子 rch, 则 key [p]\(\lt\) key [rch]; 注意, 本题中的二叉搜索树应满足对于所有结点, 其左子树中的 key 小于 当前结点的 key, 其右子树中的 key 大于当前结点的 key.
小 Y 与他人讨论的内容则是, 现在给定一棵二叉树, 可以任意修改结点的数值. 修改一个结点的数值算作一次修改, 且这个结点不能再被修改. 若要将其变成一棵二叉搜索树, 且任意时刻结点的数值必须是整数 (可以是负整数或 0), 所要的最少修改次数.
相信这一定难不倒你! 请帮助小 Y 解决这个问题吧.
输入格式
第一行一个正整数 n 表示二叉树结点数. 结点从 1~ n 进行编号.
第二行 n 个正整数用空格分隔开, 第 i 个数 ai 表示结点 i 的原始数值.
此后 n-1 行每行两个非负整数 fa, ch, 第 i+2 行描述结点 i+1 的父亲编号 fa, 以及父子关系 ch, (ch=0 表示 i+1 为左儿子, ch=1 表示 i+1 为右儿子).
结点 1 一定是二叉树的根.
输出格式
仅一行包含一个整数, 表示最少的修改次数.
样例输入 1
3
2 2 2
1 0
1 1样例输出 1
2样例输入 2
7
6 2 5 3 4 7 2
1 1
2 1
3 1
4 1
5 1
6 1样例输出 2
4数据范围
20%:\(n \leq 10 , a_i \leq 100\).
40%:\(n \leq 100 , a_i \leq 200\)
60%:\(n \leq 2000\).
100%:\(n \leq 10^5 , a_i \lt 2^{31}\).
Explanation
就是一道巨水 DP 题. 简单的来讲, 我们可以先求出这棵树的先序遍历, 然后就把一个在树上的复杂问题变成了一个在序列上瞎搞的题目......
然后问题就变成一个类 最长非降子序列的问题. 这样看来, 将每一个数加上当前所在位置的哈希 (所谓哈希, 就是 \(n - i\)) . 最后就变成了求一个序列的最长非降子序列.
但是写了很久还是没有 AC. 为什么呢? 因为我又 作死写了一个 Splay 然后调了一整下午三个小时都不停地死循环+TLE+WA+RE+CE (233)~
其他的做法还有:
- 神奇优化线段树 (先离散化, 然后在线段树上区间最大区间修改), 就是我的 AC 做法.
- 玄学二分做法 ((@MisakiHanayo 的做法)
- 还有比较正常的堆~
Splay 能干的事, 没有什么不是 Heap 不能干的事.
世界上没有什么问题不是 Heap 不能干的事. 如果有, 那就是可持久化 Heap.
Source Code
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long lli;
const int maxn = 200100;
class SegmentTree
{
public:
int n, lbnd[maxn], rbnd[maxn], vmx[maxn], lazy[maxn];
void build_tree(int n_) {
n = 1; while (n < n_) n *= 2;
for (int i = 1; i <= n; i++) {
lbnd[i + n - 1] = rbnd[i + n - 1] = i;
vmx[i + n - 1] = lazy[i + n - 1] = 0; }
for (int i = n - 1; i >= 1; i--) {
lbnd[i] = lbnd[i * 2];
rbnd[i] = rbnd[i * 2 + 1];
vmx[i] = lazy[i] = 0; }
return ; }
void dispatch_lazy(int p) {
lazy[2 * p] = max(lazy[2 * p], lazy[p]);
lazy[2 * p + 1] = max(lazy[2 * p + 1], lazy[p]);
vmx[p] = max(vmx[p], lazy[p]);
lazy[p] = 0; }
int query(int p, int l, int r) {
if (l == lbnd[p] && r == rbnd[p])
return max(vmx[p], lazy[p]);
dispatch_lazy(p);
if (r <= rbnd[2 * p]) return query(2 * p, l, r);
else if (l >= lbnd[2 * p + 1]) return query(2 * p + 1, l, r);
return max(query(2 * p, l, rbnd[2 * p]), query(2 * p + 1, lbnd[2 * p + 1], r)); }
void change(int p, int l, int r, int v) {
if (l == lbnd[p] && r == rbnd[p]) {
lazy[p] = max(lazy[p], v);
return ; }
dispatch_lazy(p);
if (r <= rbnd[2 * p]) change(2 * p, l, r, v);
else if (l >= lbnd[2 * p + 1]) change(2 * p + 1, l, r, v);
else change(2 * p, l, rbnd[2 * p], v), change(2 * p + 1, lbnd[2 * p + 1], r, v);
vmx[p] = max(max(vmx[2 * p], lazy[2 * p]), max(vmx[2 * p + 1], lazy[2 * p + 1])); }
public:
int query(int l, int r) {
if (l > r) return 0;
return query(1, l, r); }
void change(int l, int r, int v) {
if (l > r) return ;
change(1, l, r, v); }
} st;
struct srtr { int a, b; };
bool cmp(srtr a, srtr b) { return a.a < b.a; };
class DistributionReduction
{
public:
int n;
int arr[maxn];
srtr srt[maxn];
int eval(int n) {
this->n = n;
for (int i = 1; i <= n; i++) {
srt[i].a = arr[i];
srt[i].b = i;
}
sort(srt + 1, srt + 1 + n, cmp);
int ncnt = 0;
for (int i = 1; i <= n; i++)
arr[srt[i].b] = (srt[i].a > srt[i - 1].a) ? (++ncnt) : (ncnt);
return ncnt; }
} dr;
int n, root, arr_cnt;
int ch[maxn][2];
int val[maxn], arr[maxn];
int dp[maxn];
void dfs_tree(int p)
{
if (p == 0)
return ;
// If this is not a null sequence, make some modifications
dfs_tree(ch[p][0]);
arr[++arr_cnt] = val[p];
dfs_tree(ch[p][1]);
return ;
}
int main(int argc, char** argv)
{
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &val[i]);
for (int i = 2, a, b; i <= n; i++) {
scanf("%d%d", &a, &b);
ch[a][b] = i;
}
// Done inputting data, now processing tree into a sequence.
dfs_tree(1);
// Pre-processing a sequence.
// Obviously the datum must be added with its successive number.
for (int i = 1; i <= n; i++)
arr[i] -= i - n;
// Pre-saving data orientation with sorting techniques
for (int i = 1; i <= n; i++) dr.arr[i] = arr[i];
int m = dr.eval(n); // Sorting and evaluating...
for (int i = 1; i <= n; i++) arr[i] = dr.arr[i];
// Dynamic programming (with segment tree optimisation)
st.build_tree(m);
for (int i = 1; i <= n; i++) {
// dp[i] = 1;
// for (int j = 1; j < i; j++)
// if (arr[j] <= arr[i])
// dp[i] = max(dp[i], dp[j] + 1);
int j = st.query(1, arr[i]);
dp[i] = j + 1;
st.change(arr[i], m, dp[i]);
}
int res = n;
for (int i = 1; i <= n; i++)
res = min(res, n - dp[i]);
printf("%d\n", res);
return 0;
}以下是 WA 掉的代码. 虽然不会 CE, 但是请诸位大神慎入~
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
typedef long long lli;
const int maxn = 200100;
const int infinit = 1000000007;
class SplayTree
{
public:
int ch[maxn][2], parent[maxn], root, ncnt, n;
int val[maxn], dat[maxn], maxx[maxn];
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
#define par(x) parent[x]
int makenode(int q, int v, int w)
{
int p = ++ncnt; n++;
lc(p) = rc(p) = 0;
par(p) = q;
val[p] = v;
dat[p] = maxx[p] = w;
return p;
}
void updatemaxx(int p)
{
maxx[p] = p > 2 ? dat[p] : 0;
if (lc(p)) maxx[p] = max(maxx[p], maxx[lc(p)]);
if (rc(p)) maxx[p] = max(maxx[p], maxx[rc(p)]);
return ;
}
void rotate(int p)
{
int q = par(p), g = par(q), x = p == rc(q);
// Relink connexions between nodes
ch[q][x] = ch[p][!x], par(ch[q][x]) = q;
ch[p][!x] = q, par(q) = p;
par(p) = g;
if (g) ch[g][rc(g) == q] = p;
// Update data values
updatemaxx(p);
updatemaxx(q);
if (g)
updatemaxx(g);
return ;
}
void splay(int p, int t)
{
for (int q = 0; (q = par(p)) && q != t; rotate(p))
if (par(q) && par(q) != t)
rotate((p == lc(q)) == (q == lc(par(q))) ? q : p);
if (t == 0) root = p;
return ;
}
int suc(int p)
{
if (!rc(p)) { while (p == rc(par(p))) p = par(p); p = par(p); }
else { p = rc(p); while (lc(p)) p = lc(p); }
return p;
}
int find(int x)
{
int p = root;
while (p && (lc(p) || rc(p))) {
if (x < val[p])
p = lc(p);
else if (x == val[p])
return p;
else
p = rc(p);
}
return p;
}
void insert(int v, int w)
{
int lp = find(v), rp = suc(lp);
splay(rp, 0);
splay(lp, root);
int c = makenode(lp, v, w);
rc(lp) = c;
updatemaxx(lp);
updatemaxx(rp);
return ;
}
void modify(int v, int w)
{
printf("modify %d %d\n", v, w);
int p = find(v);
if (!p)
return ;
if (val[p] != v) {
insert(v, w);
return ;
}
splay(p, 0);
dat[p] = w;
updatemaxx(p);
return ;
}
int query_max(int l, int r)
{
int lp = find(l), rp = find(r);
printf("query max %d %d %d %d\n", l, r, lp, rp);
splay(rp, 0);
splay(lp, root);
// Return data values
int res = maxx[rc(lp)];
if (dat[lp] >= l)
res = max(res, dat[lp]);
if (dat[rp] <= r)
res = max(res, dat[rp]);
return res;
}
void buildtree()
{
n = ncnt = 0;
root = makenode(0, -2, 0);
rc(root) = makenode(root, infinit, 0);
maxx[1] = maxx[2] = infinit;
par(rc(root)) = root;
return ;
}
} sp;
int n, root, arr_cnt;
int ch[maxn][2];
int val[maxn], arr[maxn];
int dp[maxn];
void dfs_tree(int p)
{
if (p == 0)
return ;
// If this is not a null sequence, make some modifications
dfs_tree(ch[p][0]);
arr[++arr_cnt] = val[p];
dfs_tree(ch[p][1]);
return ;
}
int main(int argc, char** argv)
{
// sp.buildtree();
// sp.modify(0, 0);
// sp.modify(12, 1);
// sp.modify(7, 1);
// sp.modify(9, 1);
// sp.modify(6, 1);
// sp.modify(6, 1);
// sp.modify(8, 1);
// sp.modify(2, 1);
// sp.query_max(1, 7);
// return 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &val[i]);
for (int i = 2, a, b; i <= n; i++) {
scanf("%d%d", &a, &b);
ch[a][b] = i;
}
// Done inputting data, now processing tree into a sequence.
dfs_tree(1);
// Pre-processing a sequence.
// Obviously the datum must be added with its successive number.
for (int i = 1; i <= n; i++)
arr[i] -= i - n;
// As the splay tree has problems...
sp.buildtree();
sp.modify(0, 0);
sp.insert(infinit - 1, 0);
set<int> st; st.insert(-0);
// Now checking incrementation status
for (int i = 1; i <= n; i++) {
dp[i] = 1;
// for (int j = 1; j < i; j++)
// if (arr[j] <= arr[i])
// dp[i] = max(dp[i], dp[j] + 1);
int j = arr[i]; // Find exact data, smaller than arr[i]
int v = sp.query_max(0, j);
printf("dping %d %d %d\n", i, j, v);
dp[i] = v + 1;
sp.modify(arr[i], dp[i]);
st.insert(-arr[i]);
}
// Processing best selection
int res = n;
for (int i = 1; i <= n; i++)
res = min(res, n - dp[i]);
printf("%d\n", res);
return 0;
}