可持久化 5pts 求条
查看原帖
可持久化 5pts 求条
1367000
Ybll_楼主2025/6/30 11:38
#include<bits/stdc++.h>
#define int long long
#define il inline
using namespace std;
const int N=400005;
struct G
{
	int next,to,val,sum;
}g[N];
struct edge
{
	int u,v,val,sum;
}edge[N];
struct query
{
	int val,sum;
}q[N],f[11][N];
struct segment_tree
{
	int ls,rs,sum,l,r;
}tree[N<<5];
int head[N],cnt,n,m,ans,sum[N],root[N],A[N];
void add(int u,int v,int w1,int w2)
{
	g[++cnt]={head[u],v,w1,w2};
	head[u]=cnt;
}
bool cmp(query i,query j)
{
	return i.sum<j.sum||i.sum==j.sum&&i.val<j.val;
}
il void new_node(int &x)
{
	tree[++cnt]=tree[x];
	tree[cnt].sum++;
	x=cnt;
}
il void build(int &id,int l,int r)
{
	id=++cnt;
	tree[id].l=l;
	tree[id].r=r;
	if(l==r)return;
	int mid=l+r>>1;
	build(tree[id].ls,l,mid);
	build(tree[id].rs,mid+1,r);
}
il void update(int &id,int p)
{
	if(tree[id].l>p||tree[id].r<p)return;
	new_node(id);
	if(tree[id].l==tree[id].r)return;
	update(tree[id].ls,p);
	update(tree[id].rs,p);
}
il int query(int idx,int idy,int x)
{
	if(tree[idx].l>=tree[idx].r)return tree[idx].l;
	int i=tree[tree[idy].ls].sum-tree[tree[idx].ls].sum;
	if(i>=x)return query(tree[idx].ls,tree[idy].ls,x);
	return query(tree[idx].rs,tree[idy].rs,x-i);
}
void dfs(int u,int dep)
{
	for(int i=head[u];i;i=g[i].next)
	{
		sum[g[i].to]=g[i].sum+sum[u];
		root[g[i].to]=root[u];
		update(root[g[i].to],g[i].val);
		for(int j=0;j<min(11ll,dep);j++)
		{
			f[j][g[i].to].sum=query(root[1],root[g[i].to],dep-j);
		}
		dfs(g[i].to,dep+1);
	}
}
signed main()
{
//	freopen("skiing.in","r",stdin);
//	freopen("skiing.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=2,j,k,l;i<=n;i++)
	{
		cin>>j>>k>>l;
		edge[i-1]={j,i,k,l};
		A[i-1]=k;
	}
	sort(A+1,A+n);
	A[0]=unique(A+1,A+n)-A-1;
	build(root[1],1,A[0]);
	A[0]=0;
	for(int i=1;i<n;i++)
	{
		edge[i].val=lower_bound(A+1,A+n,edge[i].val)-A;
		add(edge[i].u,edge[i].v,edge[i].val,edge[i].sum);
	}
	dfs(1,1);
	for(int i=0;i<11;i++)
	{
		for(int j=1;j<=n;j++)
		{
			f[i][j].sum=A[f[i][j].sum];
			f[i][j].val=sum[j];
		}
		sort(f[i]+1,f[i]+1+n,cmp);
	}
	cin>>m;
	while(m--)
	{
		int a,b,l=1,r=n,mid,res;
		cin>>a>>b;
		while(l<=r)
		{
			mid=l+r>>1;
			if(f[b][mid].sum<=a)
			{
				res=f[b][mid].val;
				l=mid+1;
			}
			else r=mid-1;
		}
		cout<<res<<"\n";
	}
	return 0;
}
2025/6/30 11:38
加载中...