HDU 4366(Successor-块状链表)

给一棵树(2<=n<=50000)个节点，每个节点有2个点权”忠诚”与”能力”
所有节点”忠诚”各不相同，现在有m个询问，每次对第i个节点，求出其子树中”能力”>它的节点中”忠诚”最高的那个

先求出dfs序，分n√段
每段按能力排序，预处理每段到i到末尾能取的最大忠诚
复杂度O(nn√logn)

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cmath>
#include<cctype>
#include<ctime>
#include<map>
#include<iomanip>
#include<vector>
using namespace std;
#define For(i,n) for(int i=1;i<=n;i++)
#define Fork(i,k,n) for(int i=k;i<=n;i++)
#define Rep(i,n) for(int i=0;i<n;i++)
#define ForD(i,n) for(int i=n;i;i--)
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define ForkD(i,k,n) for(int i=n;i>=k;i--)
#define RepD(i,n) for(int i=n;i>=0;i--)
#define Forp(x) for(int p=Pre[x];p;p=Next[p])
#define Forpiter(x) for(int &p=iter[x];p;p=Next[p])
#define Lson (o<<1)
#define Rson ((o<<1)+1)
#define MEM(a) memset(a,0,sizeof(a));
#define MEMI(a) memset(a,127,sizeof(a));
#define MEMi(a) memset(a,128,sizeof(a));
#define INF (2139062143)
#define F (100000007)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define vi vector<int>
#define pi pair<int,int>
typedef long long ll;
typedef unsigned long long ull;
ll mul(ll a,ll b){return (a*b)%F;}
ll add(ll a,ll b){return (a+b)%F;}
ll sub(ll a,ll b){return (a-b+llabs(a-b)/F*F+F)%F;}
void upd(ll &a,ll b){a=(a%F+b%F)%F;}
int read()
{
int x=0,f=1; char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}
while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
#define MAXN (55000+10)
int n,m;
vi e[MAXN];
int l[MAXN],r[MAXN],ti[MAXN];
pi a[MAXN];
void dfs(int x,int &T) {
l[x]=++T;
ti[T]=x;
for(auto v:e[x]) {
dfs(v,T);
}
r[x]=T;
}
map<int,int> h;
int blo,le;
int cmp(int x,int y) {
if (x==-1||y==-1) return x<y;
return a[x].fi<a[y].fi;
}
int sorted[MAXN],ma[MAXN];

int work(int l,int r,int x) {
int ans=r+1;
while (l<=r) {
int m=(l+r)>>1;
if (a[sorted[m]].fi <=x) l=m+1;
else r=m-1,ans=m;
}
return ans;
}


int main()
{
// freopen("hdu4366_data.out","r",stdin);
// freopen("hdu4366.out","w",stdout);

int T=read();
while(T--) {
h.clear();
int n=read(),m=read();
For(i,n-1) {
int u=read();
e[u].pb(i);
a[i].se=read(); a[i].fi=read();
h[a[i].se]=i;
}
int t=0;
dfs(0,t);

blo=250;
le=t/blo;

For(i,t) sorted[i]=ti[i];

For(i,le)
{
sort(sorted+(i-1)*blo+1,sorted+i*blo+1,cmp);
}

ForD(i,le*blo) {
ma[i]=a[sorted[i]].se;
if (i%blo)
ma[i]=max(ma[i],ma[i+1]);
}

while(m--) {
int x;
scanf("%d",&x);
int L=l[x]+1,R=r[x];
if (L>R) {printf("-1\n");continue;}
int ans=-1;
for(int i=L;i<=R;)
if ( i % blo == 1 && i + blo - 1 <= R ) {
if (a[sorted[i+blo-1]].fi<=a[x].fi ) {
i+=blo;
continue;
}
if (a[sorted[i]].fi>a[x].fi) {
ans=max(ans, ma[i] );
i+=blo;
continue;
} //这个优化必选加
// int p=upper_bound(sorted+i+1,sorted+i+blo,x,cmp)-(sorted); //这个函数不快但可用
int p=work(i,i+blo-1,a[x].fi);
if (p!=i+blo) {
ans=max(ans,ma[p]);
}
i+=blo;
} else {
if (a[x].fi<a[ti[i]].fi ) ans=max(ans,a[ti[i]].se);
i++;
}
printf("%d\n",ans==-1 ? ans:h[ans]);
}


Rep(i,n) e[i].clear();

}
return 0;
}