洛谷题面

顺着树剖的推荐题目点进来的，没想到压根不是树剖，代码还很短 \(\verb!qwq!\)。

题目大意

给定一棵 \(\rm BST\)，但是不保证这是一棵正确的 \(\rm BST\)。

请计算有多少节点不会被遍历到。

题目分析

在 \(\rm BST\) 中，节点 \(u\) 一定满足 \(val[ls(u)]val[u]\)，根据这个性质，一个数能够被找到当且仅当 \(l。

在 \(\rm dfs\) 过程中，我们使用 \(map\) 来映射每个节点是否被找到，最后查找就很方便。

于是就做完了。

代码

注意 dfs(rt,-1,1e9+1)，因为 \(\rm dfs\) 中我们是 < 和 >，所以这里应当满足 \(l\ge0-1,r\le10^9+1\)。

//2022/1/3

const int ma=1e5+5;

int a[ma],ls[ma],rs[ma];

bool have_fa[ma];

int n;

mapmp;

inline void dfs(int now,int l,int r)
{
	if(now==-1)
	{
		return;
	}
	
	if(a[now]>l && a[now]