1 /*

  2 题意：

  3 一共有n个人，其中0号是总裁(金字塔顶尖)。后面输入其他n-1个人的信息啊a、b、c，分别代表第i个人的上级是a，他的

  4 忠诚度为b，他的能力为c。后面有m次询问。他问你能不能找到一个能力比他高的，且忠诚度最高的人。(注意能力只需要

  5 大于此人就可以，不需要最高）

  6

  7

  8 题解：

  9 这道题目用的是分块的方法

 10

 11 首先需要跑一遍dfs来确定每一个人所处于金字塔的位置。从总裁开始向他的下属跑dfs(注意是dfs不是bfs)

 12 因为这样我们最后会得到一个pre数组和一个last数组。这两个数组的作用就是来看某个人x他在金字塔中的位置

 13 以及他的下属最大的位置(这个位置的值是cnt)。那么pre[x]到last[x]之间的所有人都是x的下属

 14

 15 然后分块也是按照位置的编号进行分块的，这个样子维护也好维护。分块后会得到一个maxx数组，这个数组的作用就是

 16 maxx[x][y]：在第x个块里，能力大于y且忠诚度最高的值，这个p[x][y]存放的是这个值所对应的人

 17

 18 id数组里面放的是就是，id[x]表示：位置为x的人的在输入中的编号是多少

 19

 20 具体看代码

 21 */

 22 #include<stdio.h>

 23 #include<string.h>

 24 #include<iostream>

 25 #include<algorithm>

 26 #include<math.h>

 27 #include<vector>

 28 using namespace std;

 29 const int maxn=50005;

 30 const int maxm=sqrt(50000)+5;

 31 int n,m,block,num;

 32 int belong[maxn],l[maxn],r[maxn],last[maxn],cnt=0,pre[maxn];

 33 int id[maxn],v[maxn],a[maxn],maxx[maxm][maxm],p[maxm][maxm];

 34 struct node

 35 {

 36     int ability,loyalty,id;

 37     node(int l=0,int a=0,int id=0):loyalty(l),ability(a),id(id) {};

 38     bool operator <(const node& r)const

 39     {

 40         return ability<r.ability;

 41     }

 42 } c[maxn];

 43 vector<node>b[maxn];

 44 vector<int>g[maxn];

 45 void build()

 46 {

 47     block = sqrt(n);

 48     num = n / block;

 49     if(n % block) num++;

 50     for(int i = 1; i <= num; i++)

 51     {

 52         l[i] = (i-1)*block+1;

 53         r[i] = i*block;

 54     }

 55     r[num] = n;

 56     for(int i = 1; i <= n; i++)

 57     {

 58         belong[i] = (i-1)/block+1;

 59     }

 60     for(int i = 1; i <= num; i++)

 61     {

 62         for(int j = l[i]; j <= r[i]; j++)

 63         {

 64             int idd = id[j];

 65             c[j] = node(v[idd], a[idd], idd);

 66             b[i].push_back(node(v[idd], a[idd], idd));

 67         }

 68         sort(b[i].begin(), b[i].end());

 69         int len = b[i].size();

 70         maxx[i][len] = -1;

 71         for(int j = len-1; j >= 0; j--)

 72         {

 73             if(maxx[i][j+1] < b[i][j].loyalty)

 74             {

 75                 maxx[i][j] = b[i][j].loyalty;

 76                 p[i][j] = b[i][j].id;

 77             }

 78             else

 79             {

 80                 maxx[i][j] = maxx[i][j+1];

 81                 p[i][j] = p[i][j+1];

 82             }

 83         }

 84     }

 85 }

 86 int query(int fa,int x,int y)

 87 {

 88     int ans=-1,id=-1;

 89     if(belong[x]==belong[y])

 90     {

 91         for(int i=x; i<=y; ++i)

 92         {

 93             if(a[fa]<c[i].ability && ans<c[i].loyalty)

 94             {

 95                 ans=c[i].loyalty;

 96                 id=c[i].id;

 97             }

 98         }

 99     }

100     else

101     {

102         for(int i=x; i<=r[belong[x]]; ++i)

103         {

104             if(a[fa]<c[i].ability && ans<c[i].loyalty)

105             {

106                 ans=c[i].loyalty;

107                 id=c[i].id;

108             }

109         }

110

111         for(int i=belong[x]+1; i<belong[y]; ++i)

112         {

113             int pos = upper_bound(b[i].begin(), b[i].end(), node(0, a[fa], 0)) - b[i].begin();

114             int cur = maxx[i][pos];

115             if(ans < cur)

116             {

117                 ans = cur;

118                 id = p[i][pos];

119             }

120         }

121

122         for(int i=l[belong[y]]; i<=y; ++i)

123         {

124             if(a[fa]<c[i].ability && ans<c[i].loyalty)

125             {

126                 ans=c[i].loyalty;

127                 id=c[i].id;

128             }

129         }

130     }

131     return id;

132 }

133 void init()

134 {

135     for(int i=0; i<=n; ++i)

136     {

137         b[i].clear();

138         g[i].clear();

139     }

140     cnt=0;

141 }

142 void dfs(int root,int fa)

143 {

144     pre[root]=++cnt;

145     id[cnt]=root;

146     int len=g[root].size();

147     for(int i=0; i<len; ++i)

148     {

149         int v=g[root][i];

150         if(v!=fa) dfs(v,root);

151     }

152     last[root]=cnt;

153 }

154 int main()

155 {

156     int t;

157     scanf("%d",&t);

158     while(t--)

159     {

160         scanf("%d%d",&n,&m);

161         init();

162         for(int i=1; i<=n-1; ++i)

163         {

164             int x;

165             scanf("%d%d%d",&x,&v[i],&a[i]);

166             g[x].push_back(i);

167         }

168         dfs(0,0);

169         build();

170         while(m--)

171         {

172             int x;

173             scanf("%d",&x);

174             printf("%d\n",query(x,pre[x],last[x]));

175         }

176     }

177     return 0;

178 }