Successor

线段树
map离散化，按照能力值排序建立更新节点，区间查询（单点更新）

for (int i=1;i<=n-1;i++)
	   {  scanf("%d%d%d",&fa,&peo[i].loty,&peo[i].abty);
	      peo[i].id=i;
		  son[fa].push_back(i);
		  D[peo[i].loty]=i; 
		}	

离散化

cmp排序（能力相同返回序号小的）

bool cmp(node A,node B){
  if (A.abty==B.abty) return A.id<B.id;
     else return A.abty>B.abty;	
}

单点更新

void update(int k,int val,int rt,int l,int r){
	if (l==r) {
		tree[rt]=val;return;
	}
	int mid=(l+r)>>1;
	if (k<=mid) update(k,val,rt<<1,l,mid);
	else update(k,val,rt<<1|1,mid+1,r);
	tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
} 
区间查询
int ask(int L,int R,int rt,int l,int r){
	if (L>R) return -1;
	if (L<=l&&r<=R) return tree[rt];
    int mid=(l+r)>>1,ansl=-1,ansr=-1;
    if (L<=mid) ansl=ask(L,R,rt<<1,l,mid);
    if (R>mid) ansr=ask(L,R,rt<<1|1,mid+1,r);
    return max(ansl,ansr);
}

dfs序树
今天刚学了taijian，还是挺好理解的（vector写法）

void dfs(int u)
{
	L[u]=tot++;
	for (int i=0;i<son[u].size();i++) dfs(son[u][i]);
	R[u]=tot;
}

邻接表写法

void dfs(int u)
{
l[u]=tot++;
for (int i=head[u];i;i=e[i].nxt)
     {
     int v=e[i].to;
       dfs(v); 
     }
    r[u]=tot;
}

ans 边处理边记录，化查询为离线

dfs(0);
	  sort(peo+1,peo+n,cmp);//按能力值排序
	  for (int i=1;i<n;i++){
	  	int id=peo[i].id;
	  	update(L[id],peo[i].loty,1,0,n-1);
	  	if (son[id].size()==0){
	  		ans[id]=-1;
	  		continue;
		  }
		int s=ask(L[id]+1,R[id]-1,1,0,n-1);
		if (s!=-1) ans[id]=D[s];
		  else ans[id]=-1;
	  }