传送门 问题：给出一棵树，除根结点(0)以外每个点有一个能力值和忠诚度，查询u所在子树结点中找一个能力值比u高并且忠诚度尽量大的点，输出其编号。
按能力值从高到低排序，建出线段树维护区间最大值，跑出dfs序后，先查询，再插入。
#pragma comment(linker,"/STACK:1024000000,1024000000") #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #include<map> #include<vector> #include<cstdlib> #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define root 1,1,n-1 using namespace std; const int maxn=5e4+2; int n,m; vector<int> G[maxn]; map<int,int> mp; struct NODE { int id,ab,lo; friend bool operator <(const NODE &a,const NODE &b) { return a.ab>b.ab||(a.ab==b.ab&&a.id<b.id); } }ff[maxn]; int in[maxn],out[maxn],tim; int maxx[maxn<<2],q[maxn]; inline int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar(); return x*f; } inline void pushup(int rt) { maxx[rt]=max(maxx[rt<<1],maxx[rt<<1|1]); } void build(int rt,int l,int r) { if (l==r) { maxx[rt]=-1; return ; } int mid=(l+r)>>1; build(lson), build(rson), pushup(rt); } void modify(int rt,int l,int r,int pos,int val) { if (l==r) { maxx[rt]=val; return ; } int mid=(l+r)>>1; if (pos<=mid) modify(lson,pos,val); else modify(rson,pos,val); pushup(rt); } int query(int rt,int l,int r,int L,int R) { if (L<=l&&r<=R) return maxx[rt]; int mid=(l+r)>>1,ret=-1; if (L<=mid) ret=max(ret,query(lson,L,R)); if (mid<R) ret=max(ret,query(rson,L,R)); return ret; } void dfs(int p,int f) { in[p]=tim++; int siz=G[p].size(); for (int i=0;i<siz;++i) { int v=G[p][i]; if (v==f) continue; dfs(v,p); } out[p]=tim-1; } int main() { // freopen("hdu 4366.in","r",stdin); int kase=read(); while (kase--) { n=read(),m=read(); for (register int i=0;i<n;++i) G[i].clear(); mp.clear(),mp[-1]=-1,tim=0; for (register int i=1;i<n;++i) { int fa=read(); G[fa].push_back(i); ff[i].lo=read(),ff[i].ab=read(),ff[i].id=i; mp[ff[i].lo]=i; } sort(ff+1,ff+n); build(root); dfs(0,0); for (register int i=1;i<n;++i) { int tmp=query(root,in[ff[i].id],out[ff[i].id]); q[ff[i].id]=mp[tmp]; modify(root,in[ff[i].id],ff[i].lo); } while (m--) { int x=read(); printf("%d\n",q[x]); } } return 0; }