给一棵树(2<=n<=50000)个节点，每个节点有2个点权”忠诚”与”能力” 所有节点”忠诚”各不相同，现在有m个询问，每次对第i个节点，求出其子树中”能力”>它的节点中”忠诚”最高的那个
先求出dfs序，分n√段 每段按能力排序，预处理每段到i到末尾能取的最大忠诚 复杂度O(nn√logn)
#include#include#include#include#include#include#include#include#include#include#include #includeusing 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 #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;}
