【题目链接】 http://acm.hdu.edu.cn/showproblem.php?pid=4366
【题目大意】
有一个公司，每个员工都有一个上司，所有的人呈树状关系，现在给出每个人的忠诚值和能力值，每次当一个人被辞退的时候，会由能力值大于他的下属中忠诚值最高的去代替他的位置，下属的关系是可传递的，上司的编号一定大于下属。现在给出一些询问，问如果一个人辞退将会由哪个人代替他，所有人的忠诚值都是唯一的。
【题解】
现在这道题就相当于是从子树中找出key1值大于子树根节点且key2值最高的子节点。首先，单纯考虑key2值最高的问题，发现只要树链剖分一下线段树维护RMQ即可，对于key1值的处理问题，我们考虑扫描线算法，将节点按照key1值降序扫描，那么在顺序统计答案的时候，只会统计到大于等于key1值的子节点，特别的，为处理等于的问题，在key1值相同的情况下，优先扫描编号小的节点，就不会出现统计了key1值相同的子节点的情况了。因为忠诚值唯一，所以只需用zkw线段树维护key2单值，在忠诚值和编号之间做一个单映射就可以得到需要输出的答案。
【代码】
#include <cstdio>
#include <algorithm>
#include <climits>
#include <cstring>
using namespace std;
const int N=100010;
int tot,x,d[N],num[N],ed=0,u,w,n,m,i;
int v[N],vis[N],f[N],g[N],nxt[N],size[N],son[N],st[N],en[N],dfn,top[N],t;
void add(int x,int y){v[++ed]=y;nxt[ed]=g[x];g[x]=ed;}
void dfs(int x){
size[x]=1;
for(int i=g[x];i;i=nxt[i])if(v[i]!=f[x]){
f[v[i]]=x,d[v[i]]=d[x]+1;
dfs(v[i]),size[x]+=size[v[i]];
if(size[v[i]]>size[son[x]])son[x]=v[i];
}
}
void dfs2(int x,int y){
if(x==-1)return;
st[x]=++dfn;top[x]=y;
if(son[x])dfs2(son[x],y);
for(int i=g[x];i;i=nxt[i])if(v[i]!=son[x]&&v[i]!=f[x])dfs2(v[i],v[i]);
en[x]=dfn;
}
void init(){
memset(g,dfn=ed=tot=0,sizeof(g));
memset(v,0,sizeof(v));
memset(nxt,0,sizeof(nxt));
memset(son,-1,sizeof(son));
}
struct person{int id,a,b,c;}p[N];
bool cmp(person a,person b){return a.c==b.c?a.id<b.id:a.c>b.c;}
int M,Cas,T[N*4],ans[N],Hash[1000005];
int main(){
scanf("%d",&Cas);
while(Cas--){
init();
scanf("%d%d",&n,&m);
for(int i=2;i<=n;i++){
scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);
add(p[i].a+1,i);
p[i].id=i; Hash[p[i].b]=i-1;
}dfs(1);dfs2(1,1);
sort(p+2,p+n+1,cmp);
memset(T,-1,sizeof(T));
for(M=1;M<(dfn+2);M<<=1);
for(int i=2;i<=n;i++){
int Ans=-1;
int x=st[p[i].id]+M-1,y=en[p[i].id]+M+1;
while(x^y^1>0){
if(~x&1)Ans=max(Ans,T[x+1]);
if(y&1)Ans=max(Ans,T[y-1]);
x>>=1;y>>=1;
}if(Ans==-1)ans[p[i].id-1]=-1;
else ans[p[i].id-1]=Hash[Ans];
T[M+st[p[i].id]]=p[i].b;
for(x=(M+st[p[i].id])/2;x;x/=2)T[x]=max(T[x<<1],T[(x<<1)^1]);
}while(m--){
int x;
scanf("%d",&x);
printf("%d\n",ans[x]);
}
}return 0;
}