$dfs$,线段树。

通过观察可以发现,某位置要能被找到,和他到根这条路上的每个节点的权值存在密切的联系,且是父节点的左儿子还是右儿子也有联系。

可以从根开始$dfs$,边走边更新线段树,如果遍历左儿子,那么将$[1,val-1]$全部加$1$,否则将$[val+1,n]$全部加$1$,回溯的时候减$1$,判断某位置能否到达可以比较单点值与深度的关系。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std; int f[400010];
int s[400010];
int res; void pushDown(int rt)
{
if(f[rt]==0) return ;
s[2*rt] += f[rt];
s[2*rt+1] += f[rt];
f[2*rt] += f[rt];
f[2*rt+1] += f[rt];
f[rt] = 0;
return ;
} void pushUp(int rt)
{
s[rt] = s[2*rt] + s[2*rt+1];
} void update(int L,int R,int val,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
s[rt] += val;
f[rt] += val;
return ;
} int m = (l+r)/2;
pushDown(rt);
if(L<=m) update(L,R,val,l,m,2*rt);
if(R>m) update(L,R,val,m+1,r,2*rt+1);
pushUp(rt);
} void query(int pos,int l,int r,int rt)
{
if(l==r)
{
res = s[rt];
return;
} int m = (l+r)/2;
pushDown(rt);
if(pos<=m) query(pos,l,m,2*rt);
else query(pos,m+1,r,2*rt+1);
pushUp(rt); } int n;
struct X
{
int val;
int left,right;
}node[100010];
int root;
int b[100010],sz;
int ans; int get(int x)
{
int L = 0,R = sz-1; while(L<=R)
{
int mid = (L+R)/2;
if(b[mid]>x) R = mid-1;
else if(b[mid] == x) return mid+1;
else L = mid+1;
}
} int u[100010]; void dfs(int x,int y)
{
query(node[x].val,1,n,1);
if(res != y) {}
else u[node[x].val]=1; if(node[x].left!=-1)
{
if(node[x].val>1) update(1,node[x].val-1,1,1,n,1);
dfs(node[x].left,y+1);
if(node[x].val>1) update(1,node[x].val-1,-1,1,n,1);
} if(node[x].right!=-1)
{
if(node[x].val<n) update(node[x].val+1,n,1,1,n,1);
dfs(node[x].right,y+1);
if(node[x].val<n) update(node[x].val+1,n,-1,1,n,1);
} } int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&node[i].val,&node[i].left,&node[i].right); for(int i=1;i<=n;i++) b[sz++] = node[i].val;
sort(b,b+sz);
for(int i=1;i<=n;i++)
{
node[i].val = get(node[i].val);
u[node[i].val]=1;
} int sum=0;
for(int i=1;i<=n;i++) sum=sum+1; for(int i=1;i<=n;i++)
{
if(node[i].left!=-1) f[node[i].left] = 1;
if(node[i].right!=-1) f[node[i].right] = 1;
} for(int i=1;i<=n;i++)
{
if(f[i]) continue;
root = i; break;
} memset(f,0,sizeof f);
memset(u,0,sizeof u);
dfs(root,0);
for(int i=1;i<=n;i++) sum=sum-u[node[i].val]; printf("%d\n",sum); return 0;
}

最新文章

  1. struts2学习笔记--拦截器(Interceptor)和登录权限验证Demo
  2. BZOJ2933: [Poi1999]地图
  3. Android 之窗口小部件详解--App Widget
  4. 重新想象 Windows 8.1 Store Apps (79) - 控件增强: MediaElement, Frame
  5. SOA之(5)——REST的SOA(SOA with REST)概念
  6. 【LeetCode】232 &amp; 225 - Implement Queue using Stacks &amp; Implement Stack using Queues
  7. spark stream初探
  8. xcode7启动页的尺寸设置
  9. POJ1422 最小路径覆盖入门
  10. Python 基本数据类型_常用功能整理
  11. JavaScript基本数据类型
  12. SQL的操作方法
  13. NIO的初步入门
  14. 认证鉴权与API权限控制在微服务架构中的设计与实现(四)
  15. 【JAVA-JDT-AST】Java抽象语法树的构建、遍历及转成dot格式(附Github源码)
  16. Innodb的内存结构
  17. JedisPool无法获得资源问题
  18. mysql5.7 初始化启动
  19. PHP根据图片制作缩略图
  20. document.getElementsByName和document.getElementById用法

热门文章

  1. 前端PHP入门-020-重点日期函数之获取时期时间信息函数
  2. Arrays.asList方法遇到的问题
  3. 【CodeForces】626 F. Group Projects 动态规划
  4. 使用Skyworking 作全链路api调用监控,Integration of Skyworking, auditing the whole chain circuit.
  5. vue使用jsx/axios拦截器设置
  6. Vue-Module
  7. 内存不够清理方法,costdown项目时如果裁剪不下来,也可以参考
  8. HDU 6198 2017沈阳网络赛 线形递推
  9. 制作一棵ztree
  10. Eloqument 学习