Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 65536/65536K (Java/Other)

题意：给出n-1个人，每个人有一个上司，编号，能力值和忠诚度，然后q个询问，问如果删除掉一个人，从他的所有下属中找到能力值比他高的人中忠诚度最高的。

题解：

首先我们想，如果没有能力值比开除的人大这个要求，那么这就是一道简单的线段树求最大值的模版题（以忠诚度建树）。那么现在加入能力值这个条件怎么办呢。

现在存在两个问题：
1.下属关系的树中每个人的编号是无规律的，如何转化为连续的编号
2.如何做到下属的能力值比上司大

我们可以将原来以下属关系建立的树通过DFS转化为DFS序，即层次遍历，这样的好处就是可以将本来没有规律的编号转换为连续的编号，每个人存的L[x]和R[x]即对于编号x的人，他的下属们的新序号即为【L[x]+1,R[x]-1】。

接下来的问题是能力值。我们可以将每个人按照能力值降序排列，依次插入到忠诚度的线段树中，插入一个人之后马上查询对于这个人而言需要谁代替（也即查找他的儿子中忠诚度最高的），这样遍历完所有人之后就可以通过O(1)的时间输出查询答案。

还有一个点就是我们从忠诚度的树中查询到的是最大忠诚度，又由于忠诚度唯一，所以将忠诚度和编号一一映射。

//
//  main.cpp
//  专题9-线段树
//
//  Created by Edwin on 2019/3/2.
//  Copyright © 2019 Edwin. All rights reserved.
//
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define eps 1e-8
#define maxn 100000+10
#define PI acos(-1.0)
#define mst(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i=0;i<a;++i)
#define FORD(i,a,b) for(int i=a;i>=b;--i)
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define sc(t) scanf("%d",&(t))
#define sc2(t,x) scanf("%d%d",&(t),&(x))
#define pr(t) printf("%d\n",(t))
#define pb push_back
#define SZ(V) (int)V.size()
#define quickcin ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define root 1,0,n-1
#define delf int m = (r + l) / 2
using namespace std;
struct node{
    int id,abt,loy;
}peo[maxn];
vector<int> g[maxn]; //原下属树
map<int,int> mp; //忠诚度和编号一一映射
int MAX[maxn<<2];//忠诚度线段树
int tot=0,L[maxn],R[maxn],ans[maxn];
int cmp(node a,node b){
    if(a.abt==b.abt) return a.id<b.id;
    return a.abt>b.abt;
}

void init(int n){
    FOR(i,0,n)
        g[i].clear();
    mst(MAX,-1);
    mst(ans,-1);
    mp.clear();
    tot=0;
}

void PushUp(int rt){
    MAX[rt]=max(MAX[rt<<1],MAX[rt<<1|1]);
}

//将q号元素的值置换为v
void update(int q, int v, int rt, int l, int r){
    if(l == r){
        MAX[rt] = v;
        return ;
    }
    delf;
    if(q <= m) update(q, v, lson);
    else update(q, v, rson);
    PushUp(rt);
}

int query(int ql,int qr,int rt,int l,int r){
    if(ql > qr) return -1;
    if(ql <= l && r <= qr){
        return MAX[rt];
    }
    delf;
    int LL = -1, RR = -1;
    if(ql <= m) LL = query(ql,qr,lson);
    if(qr > m) RR = query(ql,qr,rson);
    return max(LL,RR);
}
void dfs(int id){//转化为dfs序
    L[id]=tot++;
    FF(i,g[id].size()){
        dfs(g[id][i]);
    }
    R[id]=tot;
}

int main(){
    int T, n, q;
    sc(T);
    while(T--){
        sc2(n,q);
        init(n);
        int fa;
        for(int i=1;i<n;++i){
            scanf("%d%d%d",&fa,&peo[i].loy,&peo[i].abt);
            peo[i].id=i;
            g[fa].pb(i);
            mp[peo[i].loy]=i;
        }
        dfs(0);
        sort(peo+1,peo+n,cmp);
        for(int i=1;i<n;i++){
            update(L[peo[i].id],peo[i].loy,1,0,n-1);
            if(g[peo[i].id].size()==0){
                ans[peo[i].id]=-1;
                continue;
            }
            int q=query(L[peo[i].id]+1,R[peo[i].id]-1,1,0,n-1);
            if(q!=-1) ans[peo[i].id]=mp[q];
            else ans[peo[i].id]=-1;
            
        }
        while(q--){
            int x;
            sc(x);
            printf("%d\n",ans[x]);
        }
    }
    return 0;
}