description

analysis

堆\(+\)树上倍增
考虑后序遍历搞出\(dfs\)序，那么要填肯定是从\(dfs\)序开始填
把每个点是序里第几位看成优先级，用小根堆来维护当前空着的优先级最小的点
插入每次弹\(x\)次堆顶，然后把这些点全部打上标记，注意标记一定是先打儿子再打父亲
然后找一个点深度最浅的打过标记的祖先，由于标记肯定打完了该点到祖先的所有点，于是倍增就可以找出
找完祖先后，把该祖先入堆，删除标记即可

code

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<vector>

#include<iostream>

#define MAXN 100005

#define MAXM MAXN*2

#define ll long long

#define fo(i,a,b) for (ll i=a;i<=b;++i)

#define fd(i,a,b) for (ll i=a;i>=b;--i)

using namespace std;

vector<ll>a[MAXN];

ll b[MAXN],c[MAXN],f[MAXN],heap[MAXN],depth[MAXN];

ll pre[MAXN][17];

bool bz[MAXN];

ll n,t,tot;

inline ll read()

{

	ll x=0,f=1;char ch=getchar();

	while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}

	while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*f;

}

inline bool cmp(ll x,ll y){return f[x]<f[y];}

inline void swap(ll &x,ll &y){ll z=x;x=y,y=z;}

inline void dfs(ll x,ll y)

{

	fo(i,0,a[x].size()-1)if (a[x][i]!=y)depth[a[x][i]]=depth[x]+1,dfs(a[x][i],x);

	f[x]=++tot,pre[x][0]=y;

}

inline void insert(ll x)

{

	heap[++heap[0]]=x;ll now=heap[0];

	while (c[heap[now>>1]]>c[heap[now]] && now>1)swap(heap[now],heap[now>>1]),now>>=1;

}

inline ll get()

{

	ll tmp=heap[1],now=1;

	heap[1]=heap[heap[0]--],heap[heap[0]+1]=0;

	while ((now<<1)<=heap[0])

	{

		ll next=now<<1;

		if (next<heap[0] && c[heap[next+1]]<c[heap[next]])++next;

		if (c[heap[now]]<=c[heap[next]])break;

		swap(heap[now],heap[next]),now=next;

	}

	return tmp;

}

inline ll find(ll x)

{

	fd(i,16,0)if (bz[pre[x][i]])x=pre[x][i];

	return x;

}

int main()

{

	freopen("T1.in","r",stdin);

	n=read(),t=read();

	fo(i,1,n-1)

	{

		ll x=read(),y=read();

		a[x].push_back(y);

		a[y].push_back(x);

	}

	fo(i,1,n)sort(a[i].begin(),a[i].end()),b[i]=i;

	tot=0,dfs(1,0),sort(b+1,b+n+1,cmp);

	fo(i,1,n)c[b[i]]=i;

	fo(i,1,n)insert(b[i]);

	fo(j,1,16)fo(i,1,n)pre[i][j]=pre[pre[i][j-1]][j-1];

	while (t--)

	{

		ll op=read(),x=read(),y;

		if (op==1)

		{

			fo(i,1,x)bz[y=get()]=1;

			printf("%lld\n",y);

		}

		else

		{

			y=find(x),printf("%lld\n",depth[x]-depth[y]);

			insert(y),bz[y]=0;

		}

	}

	return 0;

}

巴特西

【JZOJ4811】排队

description

analysis

code

最新文章

热门文章