HDU4366 分块做法，程序里附的样例输出 3 和 -1。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
const int N=50005;
inline int rd()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f*=-1;c=getchar();}
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*f;
}
int n,m,t;
struct node{
	int a,b,c;
}a[N];
vector<int> G[N];
int dfn[N],siz[N],Time,ver[N];
void dfs(int u,int fath)
{
	dfn[u]=++Time,siz[u]=1,ver[Time]=u;
	for(auto v:G[u])if(v!=fath){dfs(v,u);siz[u]+=siz[v];}
}
int L[N],R[N],pos[N];
struct nnode{
	int b,c,id;
}b[N],d[N];
int c[N];
bool cmp(nnode a,nnode b)
{
	if(a.b==b.b)return a.id<b.id;
	return a.b<b.b;
}
int suf[N],tmp[N];
int query(int l,int r,int tmpp)
{
	int p=pos[l],q=pos[r],ans=-1,tt=-1;
	if(p==q)
	{
		for(int i=l;i<=r;i++)if(d[i].b>tmpp&&d[i].c>tt)tt=d[i].c,ans=d[i].id;
		return ans;
	}
	for(int i=l;i<=R[p];i++)if(d[i].b>tmpp&&d[i].c>tt)tt=d[i].c,ans=d[i].id;
	for(int i=L[q];i<=r;i++)if(d[i].b>tmpp&&d[i].c>tt)tt=d[i].c,ans=d[i].id;
	for(int i=p+1;i<q;i++)
	{
		int x=upper_bound(c+L[i],c+R[i]+1,tmpp)-(c+L[i]);
		if(tmp[x]>tt)tt=tmp[x],ans=suf[x];
	}
	if(ans==-1)return ans;
	return ans;
}
int mian()
{
	n=rd(),m=rd();t=sqrt(n),Time=0;
	memset(dfn,0,sizeof(dfn));
	memset(siz,0,sizeof(siz));
	memset(ver,0,sizeof(ver));
	memset(suf,0,sizeof(suf));
	memset(tmp,0,sizeof(tmp));
	for(int i=1;i<=n;i++)G[i].clear();
	for(int i=2;i<=n;i++)
	{
		a[i].a=rd()+1;
		a[i].b=rd(),a[i].c=rd();
		G[a[i].a].push_back(i);
		G[i].push_back(a[i].a);
	}
	dfs(1,0);
	for(int i=1;i<=n;i++)
	{
		d[i].b=b[i].b=a[ver[i]].b;
		d[i].c=b[i].c=a[ver[i]].c;
		d[i].id=b[i].id=ver[i];
	}
	for(int i=1;i<=t;i++)L[i]=(i-1)*t+1,R[i]=i*t;
	if(R[t]<n)R[t]=n;
	for(int i=1;i<=t;i++)for(int j=L[i];j<=R[i];j++)pos[j]=i;
	for(int i=1;i<=t;i++)sort(b+L[i],b+R[i]+1,cmp);
	for(int i=1;i<=n;i++)c[i]=b[i].b;
	for(int i=t;i>=1;i--)
	{
		suf[R[i]]=b[R[i]].id,tmp[R[i]]=b[R[i]].c;
		for(int j=R[i]-1;j>=L[i];j--)
		{
			if(b[j].c>tmp[j+1])suf[j]=b[j].id,tmp[j]=b[j].c;
			else suf[j]=suf[j+1],tmp[j]=tmp[j+1];
		}
	}
	while(m--){int x=rd()+1;printf("%d\n",query(dfn[x]+1,dfn[x]+siz[x]-1,a[x].b));}
	return 0;
}
int main()
{
	int T=rd();
	while(T--)mian();
	return 0;
}
/*
1
3 2
0 100 99
1 101 100
1
2
*/