https://codeforces.com/contest/797/problem/D
题目大意
给出一棵 $n \ (\le 10^5)$ 的二叉树。依次给出每个点上的权值 $v \ (0 \le v \le 10^9)$ 和其左右儿子的下标 $l, r$ 如果不存在则为 $-1$。问对于每一个树上存在的值，如果运行如下伪码，会有多少个点返回 $false$。重复数字需要重复统计。
bool find(TreeNode t, int x) {
if (t == null)
return false;
if (t.value == x)
return true;
if (x < t.value)
return find(t.left, x);
else
return find(t.right, x);
}
find(root, x);
简要题解
注意查询就是一棵标准二叉搜索树的查询。如果 $n$ 很小直接暴力就行了。
注意到：对于走到某点 $x$ 的路径，设路径中向左儿子走的节点权值集合为 $L$，向右儿子走的节点权值集合为 $R$。则可能走到 $x$ 的权值集合为 $[max(R) + 1, min(L) - 1]$ 是连续的一段。当 $x$ 的权值属于这个范围时是可被查询的。因此我们从上到下维护走到每个点时的范围即可。
特别注意：对于 $x$ 不合法不意味着子树不合法！比如下面例子。
5
\
3
\
9
这个例子显然无法查询到 $3$ 但是可以查询到 $9$。
复杂度
$T$：$O(n \log n)$ （如果用 hash 维护可行的值的话可以到 $O(n)$）
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
template<typename Func> struct YCombinatorResult {
Func func;
template<typename T>
explicit YCombinatorResult(T &&func) : func(std::forward<T>(func)) {}
template<class ...Args> decltype(auto) operator()(Args &&...args) {
return func(std::ref(*this), std::forward<Args>(args)...);
}
};
template<typename Func> decltype(auto) y_comb(Func &&fun) {
return YCombinatorResult<std::decay_t<Func>>(std::forward<Func>(fun));
}
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
const int M = 1e9;
void solve() {
int n; cin >> n;
int v, l, r;
vector<int> val(n);
vector<int> ls(n), rs(n);
vector<int> ind(n);
for (int i = 0; i < n; i++) {
cin >> v >> l >> r; l--; r--;
val[i] = v;
ls[i] = l;
rs[i] = r;
if (l >= 0) ind[l]++;
if (r >= 0) ind[r]++;
}
int rt = -1;
for (int i = 0; i < n; i++) {
if (!ind[i]) {
rt = i;
break;
}
}
set<int> vis;
y_comb([&](auto dfs, int u, int lb, int rb) -> void {
if (u < 0) return;
if (lb <= val[u] && val[u] <= rb) {
vis.insert(val[u]);
}
if (lb < val[u]) {
dfs(ls[u], lb, min(rb, val[u] - 1));
}
if (val[u] < rb) {
dfs(rs[u], max(lb, val[u] + 1), rb);
}
})(rt, 0, M);
int ans = 0;
for (int i : val) {
if (!vis.count(i)) ans++;
}
cout << ans << endl;
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] D. Magic Numbers - Educational Codeforces Round 8