$dfs$，线段树。
通过观察可以发现，某位置要能被找到，和他到根这条路上的每个节点的权值存在密切的联系，且是父节点的左儿子还是右儿子也有联系。
可以从根开始$dfs$，边走边更新线段树，如果遍历左儿子，那么将$[1,val-1]$全部加$1$，否则将$[val+1,n]$全部加$1$，回溯的时候减$1$，判断某位置能否到达可以比较单点值与深度的关系。
#include#include #include #include #include #include #include #include #include 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