本題給的是一棵樹。 然後找子孫中能力值大於父節點並且忠誠最高的。
由於樹的結構不好搞線段樹，所以要映射到一個連續序列上搞，把這個結點的子樹都能映射到一個連續區間上就好辦了。
很常見的套路就是DFS時間戳，記錄進入結點的時間戳和出結點的時間戳，兩個時間戳之間的都是這個結點的子孫結點了。
而我們要找能力值大於父節點的還得是忠誠最高的。兩個限制。
那就進行排序，按能力值從高到低排，然後按排序後的順序，對每個結點，先查詢子樹中的最大忠誠的結點，然後再更新。這樣就能保證查到的一定是能力值大於父節點的結點了
並且題目告訴我們忠誠值互不相同，那麼就省去了我們一些麻煩了。因為每個忠誠值必然對應一個唯一的序號，那麼開個 map映射一下好了。
[cpp]
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#define eps 1e-5
#define MAXN 55555
#define MAXM 111111
#define INF 1000000007
#define lch(x) x<<1
#define rch(x) x<<1|1
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
using namespace std;
int n, m;
struct P
{
int id, a, l;
bool operator <(const P &t)const
{
return a > t.a;
}
}p[MAXN];
struct EDGE
{
int v, next;
}edge[MAXM];
int head[MAXN], e;
int index, lf[MAXN], rf[MAXN];
int mx[4 * MAXN], ans[MAXN];
void init()
{
memset(head, -1, sizeof(head));
memset(ans, -1, sizeof(ans));
e = 0;
index = 0;
for(int i = 0; i <= 4 * n; i++) mx[i] = -1;
}
void add(int x, int y)
{
edge[e].v = y;
edge[e].next = head[x];
head[x] = e++;
}
void dfs(int u)
{
lf[u] = index++;
for(int i = head[u]; i != -1; i = edge[i].next)
dfs(edge[i].v);
rf[u] = index;
}
void up(int rt)
{
mx[rt] = mx[lch(rt)] > mx[rch(rt)] ? mx[lch(rt)] : mx[rch(rt)];
}
void update(int pos, int v, int l, int r, int rt)
{
if(l == r) {mx[rt] = v; return;}
int m = (l + r) >> 1;
if(pos <= m) update(pos, v, lson);
else update(pos, v, rson);
up(rt);
}
int query(int L, int R, int l, int r, int rt)
{
if(L > R) return -1;
if(L <= l && R >= r) return mx[rt];
int ret = -1;
int m = (l + r) >> 1;
if(L <= m) ret = max(ret, query(L, R, lson));
if(m < R) ret = max(ret, query(L, R, rson));
return ret;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
int x;
scanf("%d%d", &n, &m);
init();
map<int, int>mp;
for(int i = 1; i < n; i++)
{
scanf("%d%d%d", &x, &p[i].l, &p[i].a);
p[i].id = i;
mp[p[i].l] = i;
add(x, i);
}
sort(p + 1, p + n);
dfs(0);
for(int i = 1; i < n;)
{
int pos = i;
while(pos < n && p[pos].a == p[i].a)
{
int id = p[pos].id;
int tmp = query(lf[id] + 1, rf[id] - 1, 0, index - 1, 1);
if(tmp == -1) ans[id] = -1;
else ans[id] = mp[tmp];
pos++;
}
pos = i;
while(pos < n && p[pos].a == p[i].a)
{
int id = p[pos].id;
update(lf[id], p[pos].l, 0, index - 1, 1);
pos++;
}
i = pos;
}
while(m--)
{
scanf("%d", &x);
printf("%d\n", ans[x]);
}
}
return 0;
