本文共 1156 字，大约阅读时间需要 3 分钟。
思路：
二叉搜索树；
它时间很优是因为每次都能把区间缩减为原来的一半；
所以，我们每次都缩减权值区间。
然后判断dis[now]是否在区间中；
代码：
#include #include #include #include #include using namespace std;#define maxn 100005#define INF 0x7fffffffint n,ch[maxn][2],dis[maxn],ans;int l[maxn],r[maxn],root;bool if_[maxn];map ma;map maa;inline void in(int &now){ int if_z=1;now=0; char Cget=getchar(); while(Cget>'9'||Cget<'0') { if(Cget=='-') if_z=-1; Cget=getchar(); } while(Cget>='0'&&Cget<='9') { now=now*10+Cget-'0'; Cget=getchar(); } now*=if_z;}void dfs(int now,int l,int r){ if(l>r) return ; if(dis[now]>=l&&dis[now]<=r) { if(!maa[dis[now]]) { ans+=ma[dis[now]]; maa[dis[now]]=true; } } if(ch[now][0]!=-1) dfs(ch[now][0],l,min(dis[now]-1,r)); if(ch[now][1]!=-1) dfs(ch[now][1],max(l,dis[now]+1),r);}int main(){ in(n); for(int i=1;i<=n;i++) { in(dis[i]),in(ch[i][0]),in(ch[i][1]),ma[dis[i]]++; if(ch[i][0]!=-1) if_[ch[i][0]]=true; if(ch[i][1]!=-1) if_[ch[i][1]]=true; } for(int i=1;i<=n;i++) { if(!if_[i]) { root=i; break; } } dfs(root,0,INF); cout<
转载于:https://www.cnblogs.com/IUUUUUUUskyyy/p/6839656.html