题意：每个人都有一个上司，每个人都有能力值和忠诚值，0是老板，现在给出m个询问，每次询问给出一个x，要求你找到x的所有直系和非直系下属中能力比他高的最忠诚的人是谁
思路：因为树上查询很麻烦，所以我们直接dfs序把关系变成线性。然后我们再分块，把每个块按照能力值升序排列，这样我们就能直接二分查找这个块内能力值大于x的数就是二分出来的数到块末尾的所有数。但是怎么查找最忠诚的？我们直接预处理每个块内i位置到块末尾的最忠诚人的位置就行了。
代码：
#include<set>
#include<map>
#include<stack>
#include<cmath>
#include<queue>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<sstream>
#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
const int maxn = + ;
const int MOD = 1e9 + ;
const int INF = 0x3f3f3f3f;
struct node{
int name, loyalty, ability;
bool operator < (const node &x) const{
return ability < x.ability;
}
}p[maxn];
int loyalty[maxn], ability[maxn];
int in[maxn], out[maxn]; //在dfs序列中的位置1-id
int belong[maxn], id;
int head[maxn], tot;
struct Edge{
int to, next;
}edge[maxn];
void init(){
tot = id = ;
memset(head, -, sizeof(head));
}
void addEdge(int u, int v){
edge[tot].to = v;
edge[tot].next = head[u];
head[u] = tot++;
}
void dfs(int u){
in[u] = ++id;
p[id].ability = ability[u], p[id].loyalty = loyalty[u], p[id].name = u;
for(int i = head[u]; i != -; i = edge[i].next){
int v = edge[i].to;
dfs(v);
}
out[u] = id;
}
int MaxLoy[maxn]; //从位置j到所属块末尾的最大loyalty的人在dfs序列的位置
int n, m, block, sz;
int solve(int x){
int l = belong[in[x]], r = belong[out[x]];
int L, R;
int MaxLoyalty = -, ans = -; L = block * (l - ) + , R = min(L + block - , id);
for(int i = L; i <= R; i++){
if(in[p[i].name] > in[x] && out[p[i].name] <= out[x]){
if(p[i].loyalty > MaxLoyalty && p[i].ability > ability[x]){
MaxLoyalty = p[i].loyalty;
ans = p[i].name;
}
}
}
L = l + , R = r - ;
node c;
c.ability = ability[x];
for(int i = L; i <= R; i++){
int s = block * (i - ) + , e = s + block;
int pos = upper_bound(p + s, p + e, c) - p;
if(pos >= e) continue;
int tmp = MaxLoy[pos];
if(p[tmp].loyalty > MaxLoyalty){
MaxLoyalty = p[tmp].loyalty;
ans = p[tmp].name;
}
}
L = block * (r - ) + , R = min(L + block - , id);
for(int i = L; i <= R; i++){
if(in[p[i].name] > in[x] && out[p[i].name] <= out[x]){
if(p[i].loyalty > MaxLoyalty && p[i].ability > ability[x]){
MaxLoyalty = p[i].loyalty;
ans = p[i].name;
}
}
}
return ans;
}
int main(){
int T;
scanf("%d", &T);
while(T--){
init();
int a;
scanf("%d%d", &n, &m);
ability[] = -, loyalty[] = -;
for(int i = ; i <= n - ; i++){
scanf("%d%d%d", &a, &loyalty[i], &ability[i]);
addEdge(a, i);
}
dfs();
block = (int)sqrt(id * 1.0);
for(int i = ; i <= id; i++){
belong[i] = (i - ) / block + ;
}
sz = belong[id];
for(int i = ; i <= sz; i++){
int s = block * (i - ) + , e = min(s + block, id + );
sort(p + s, p + e);
int Max = -, pos;
for(int j = e - ; j >= s; j--){
if(Max < p[j].loyalty){
Max = p[j].loyalty;
pos = j;
}
MaxLoy[j] = pos;
}
}
while(m--){
scanf("%d", &a);
printf("%d\n", solve(a));
}
}
return ;
}