求助A性质
查看原帖
求助A性质
889917
limingyuan333楼主2024/12/14 07:46
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=5e5+10;
int n;
int dep[MAXN];
struct node{
	int to,nxt;
}a[MAXN<<1];
int tot;
int head[MAXN];
void add(int x,int y){
	a[++tot].to=y;
	a[tot].nxt=head[x];
	head[x]=tot;
}
void dfs(int now,int fa){
	for(int i=head[now];i;i=a[i].nxt){
		int to=a[i].to;
		if(to==fa)	continue;
		dep[to]=dep[now]+1;
		dfs(to,now);
	}
}
int b[MAXN],c[MAXN];
void init(){
	sort(c+1,c+1+n);
	int tt=unique(1+c,1+c+n)-c-1;
	for(int i=1;i<=n;i++){
		b[i]=lower_bound(c+1,c+1+tt,b[i])-c;
	}
}
int cnt;
int rt[MAXN];
int ch[MAXN<<5][2];
int pre[MAXN<<5];
void update(int &p,int vp,int l,int r,int k){
	p=++cnt;
	ch[p][0]=ch[vp][0];
	ch[p][1]=ch[vp][1];
	pre[p]=pre[vp]+1;
	if(l==r)	return ;
	int mid=l+r>>1;
	if(k<=mid)	update(ch[p][0],ch[vp][0],l,mid,k);
	else	update(ch[p][1],ch[vp][1],mid+1,r,k);
}
int query(int p,int vp,int l,int r,int k){
	if(l==r)	return l;
	int val=pre[ch[p][0]]-pre[ch[vp][0]];
	int mid=l+r>>1;
	if(k<=val)	return query(ch[p][0],ch[vp][0],l,mid,k);
	else	return query(ch[p][1],ch[vp][1],mid+1,r,k-val);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	cin>>n;
	for(int i=1;i<n;i++){
		int u,v;cin>>u>>v;
		add(u,v),add(v,u);
	}
	dep[1]=1;
	dfs(1,0);
	for(int i=1;i<=n;i++) b[i]=dep[i],c[i]=dep[i];
	init();
	for(int i=1;i<=n;i++)	update(rt[i],rt[i-1],1,n,b[i]);
	int q;cin>>q;
	while(q--){
		int l,r,k;cin>>l>>r>>k;
		cout<<c[query(rt[r],rt[l-1],1,n,r-l+2-k)]<<'\n';
	}
	return 0;
}
2024/12/14 07:46
加载中...