题意：
现在n个人，其中编号0的是老板，之后n-1个员工，每个员工只有一个上司，有一个忠诚值和能力值。每次要解雇一个人的时候，从他的下属中选取能力值大于他的且忠诚值最高的一个，若不存在则输出-1.共m次询问，每次询问i，输出解雇i会选择哪个编号的员工代替值。（所有询问都不相互影响）
#include<bits/stdc++.h> using namespace std; #define N 50020 struct peo { int a,v,id; peo() { a=0;v=0;id=0; } }s[N]; int t[N<<2]; int cnt,n,q; vector<int>v[N]; int ha[1000020],l[N],r[N],ans[N]; void dfs(int x) { l[x]=++cnt; for(int i=0;i<v[x].size();i++) dfs(v[x][i] ); r[x]=cnt; } void build(int L,int R,int pos) { t[pos]=-1; if(L==R) return ; int mid=(L+R)>>1; build(L,mid,pos<<1 ); build(mid+1,R,pos<<1|1); } bool cmp(peo a,peo b) { return a.a>b.a; } void update(int x,int v,int L,int R,int pos) { if(L==R) { t[pos]=v; return ; } int mid=(L+R)>>1; if(x<=mid) update(x,v,L,mid,pos<<1); else update(x,v,mid+1,R,pos<<1|1); t[pos]=max(t[pos<<1],t[pos<<1|1]); } int query(int l,int r,int L,int R,int pos) { int ans=-1; if(l<=L&&r>=R) return t[pos]; int mid=(L+R)>>1; if(l<=mid)ans=max(ans,query(l,r,L,mid,pos<<1)); if(r>mid)ans=max(ans,query(l,r,mid+1,R,pos<<1|1)); return ans; } int main() { int cas;cin>>cas; while(cas--) { scanf("%d%d",&n,&q); for(int i=0;i<n;i++) v[i].clear(); for(int i=1;i<n;i++) { int pre; scanf("%d%d%d",&pre,&s[i].v,&s[i].a); v[pre].push_back(i); s[i].id=i; ha[s[i].v]=i; } cnt=0; dfs(0); build (1,n-1,1); sort(s+1,s+n,cmp); int i=1,j; while(i<n) { j=i; while(j<n&&s[i].a==s[j].a) { int k=query( l[s[j].id ],r[s[j].id ]-1,1,n-1,1 ); if(k==-1) ans[s[j].id ]=-1; else ans[s[j].id]=ha[k]; j++; } j=i; while(j<n&&s[i].a==s[j].a) { update(l[s[j].id ]-1,s[j].v,1,n-1,1 ); j++; } i=j; } while(q--) { int x; scanf("%d",&x); printf("%d ",ans[x]); } } return 0; }