洛谷题面

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

题目大意

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

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

题目分析

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

在 \(\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;

map<int,bool>mp;

inline void dfs(int now,int l,int r)
{
	if(now==-1)
	{
		return;
	}
	
	if(a[now]>l && a[now]<r)
	{
		mp[a[now]]=true;
	}
	
	dfs(ls[now],l,min(r,a[now]));
	
	dfs(rs[now],max(l,a[now]),r);
}

int main(void)
{
	n=read();
	
	for(register int i=1;i<=n;i++)
	{
		a[i]=read(),ls[i]=read(),rs[i]=read();
		
		if(ls[i]!=-1)
		{
			have_fa[ls[i]]=true;
		}
		
		if(rs[i]!=-1)
		{
			have_fa[rs[i]]=true;
		}
	}
	
	int rt;
	
	for(register int i=1;i<=n;i++)
	{
		if(have_fa[i]==false)
		{
			rt=i;
			
			break;
		}
	}
	
	dfs(rt,-1,1e9+1);
	
	int ans=0;
	
	for(register int i=1;i<=n;i++)
	{
		if(mp[a[i]]==false)
		{
			ans++;
		}
	}
	
	printf("%d\n",ans);
	
	return 0;
}