【题解】[牛客网NOIP赛前集训营-提高组（第一场）]C.保护 LCA+线段树动态开点+线段树合并

题目链接


___

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+10;
int n,m,hd[N],tot,dep[N],fa[N][20],ord[N],cnt,q;
struct Edge{
	int v,nx;
}e[N<<1];
struct SegmentTree{
	int l,r,cnt;
}c[N*100];
void add(int u,int v)
{
	e[tot].v=v;
	e[tot].nx=hd[u];
	hd[u]=tot++;
}
void dfs(int u,int f)
{
	dep[u]=dep[f]+1;
	fa[u][0]=f;
	for(int i=1;(1<<i)<=dep[u];i++)
	    fa[u][i]=fa[fa[u][i-1]][i-1];
	for(int i=hd[u];~i;i=e[i].nx)
	    if(e[i].v!=f)dfs(e[i].v,u);
}
int lca(int u,int v)
{
	if(dep[u]>dep[v])swap(u,v);
	for(int i=18;i>=0;i--)
	    if(dep[fa[v][i]]>=dep[u])v=fa[v][i];
	if(v==u)return u;
	for(int i=18;i>=0;i--)
	    if(fa[v][i]!=fa[u][i])u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
void update(int l,int r,int p,int &id)
{
	if(!id)id=++cnt;
	c[id].cnt++;
	if(l==r)return;
	int mid=l+r>>1;
	if(p<=mid)update(l,mid,p,c[id].l);
	else update(mid+1,r,p,c[id].r);
}
int merge(int l,int r,int a,int b)
{
	if((!a)||(!b))return a+b;
	int id=++cnt;
	c[id].cnt=c[a].cnt+c[b].cnt;
	if(l==r)return id;
	int mid=l+r>>1;
	c[id].l=merge(l,mid,c[a].l,c[b].l);
	c[id].r=merge(mid+1,r,c[a].r,c[b].r);
	return id;
}
void Dfs(int u,int f)
{
	for(int i=hd[u];~i;i=e[i].nx)
	    if(e[i].v!=f)
	    {
	    	Dfs(e[i].v,u);
	    	ord[u]=merge(1,n,ord[u],ord[e[i].v]);
		}
}
int find(int l,int r,int k,int id)
{
	if(c[id].cnt<k)return 0x7fffffff;
	if(l==r)return l;
	int mid=l+r>>1;
	if(c[c[id].l].cnt>=k)return find(l,mid,k,c[id].l);
	return find(mid+1,r,k-c[c[id].l].cnt,c[id].r);
}
int main()
{
	//freopen("in.txt","r",stdin);
    memset(hd,-1,sizeof(hd));
	scanf("%d%d",&n,&m);
	int u,v;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&u,&v);
		add(u,v);add(v,u);
	}
	dfs(1,0);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&u,&v);
		int p=lca(u,v);
		update(1,n,dep[p],ord[u]);update(1,n,dep[p],ord[v]);
	}
	Dfs(1,0);
	scanf("%d",&q);
	for(int i=1;i<=q;i++)
	{
		int k;
		scanf("%d%d",&u,&k);
		printf("%d\n",max(0,dep[u]-find(1,n,k,ord[u])));
	}
	return 0;
}

总结

线段树高级操作维护信息难题