自动搬运

查看原文

来自洛谷，原作者为

	_AyachiNene AFOed||私の0721を見てください！

搬运于2025-08-24 23:04:26，当前版本为作者最后更新于2025-08-20 15:03:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

首先考虑不换根的情况。一个显然的贪心，要让答案尽量小，那么每次肯定要使深度最深的点深度变小。容易发现，在保证答案不变的情况下，连向深度尽量小的点一定不劣。具体的，假设答案为 $k$，深度最大点为 $u$，那么加边就因该连在 $u$ 的 $k-1$ 级祖先上。这启发我们二分答案，判断就是直接模拟加边过程，加边部分用线段树维护深度最大点即可。这样复杂度是 $O(n^2k \log^2 n)$ 的。考虑换根，首先深度的变化是简单的，直接线段树上区间加即可，难点在于如何在换根后求出 $k$ 级祖先。假设当前的根是 $u$，最远点为 $v$，直接分讨：

1. $u$ 是 $v$ 的祖先，无影响，就是 $v$ 的 $k$ 级祖先。

2. 设 $u$ 和 $v$ 的 lca 为 $p$：

   • $dep_v-dep_p<k$，$v$ 的 $k$ 级祖先。
   • $k\leq dep_v-dep_p$，$u$ 的 $dep_u-2dep_p-k+1+dep_v$ 级祖先。

同理，可以分讨出每种情况造成的贡献，这里不再赘述。

这样复杂度是 $O(nk\log^2n)$ 的。注意到相邻点之间答案变化量不超过 $1$，就做到了 $O(nk\log n)$。

Code：

#include<bits/stdc++.h>
using namespace std;
namespace IO
{
	char buff[1<<21],*p1=buff,*p2=buff;
	char getch(){return p1==p2&&(p2=((p1=buff)+fread(buff,1,1<<21,stdin)),p1==p2)?EOF:*p1++;}
	template<typename T>void read(T &x){char ch=getch();int fl=1;x=0;while(ch>'9'||ch<'0'){if(ch=='-')fl=-1;ch=getch();}while(ch<='9'&&ch>='0'){x=x*10+ch-48;ch=getch();}x*=fl;}
	template<typename T>void read_s(T &x){x="";char ch=getch();while(!(ch>='a'&&ch<='z')&&!(ch>='A'&&ch<='Z'))ch=getch();while((ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){x+=ch;ch=getch();}}
	template<typename T,typename ...Args>void read(T &x,Args& ...args){read(x);read(args...);}
	char obuf[1<<21],*p3=obuf;
	void putch(char ch) {if(p3-obuf<(1<<21))*p3++=ch;else fwrite(obuf,p3-obuf,1,stdout),p3=obuf,*p3++=ch;}
	char ch[100];
	template<typename T>void write(T x) {if(!x)return putch('0');if(x<0)putch('-'),x*=-1;int top=0;while(x)ch[++top]=x%10+48,x/=10;while(top)putch(ch[top]),top--;}
	template<typename T,typename ...Args>void write(T x,Args ...args) {write(x);putch(' ');write(args...);}
	void put(string s){for(int i=0;i<s.size();i++)putch(s[i]);}
	void flush(){fwrite(obuf,p3-obuf,1,stdout);}
}
using namespace IO;
struct node
{
	int nxt,to;
}e[200005<<1];
int head[200005],cnt_edge;
inline void add_edge(int u,int v)
{
	e[++cnt_edge].to=v;
	e[cnt_edge].nxt=head[u];
	head[u]=cnt_edge;
}
int id,T;
int n,m,op;
#define pii pair<int,int>
#define fi first
#define se second
namespace Shiki
{
	struct segt
	{
		pii val;
		int tag;
	}t[200005<<2];
	#define ls (root<<1)
	#define rs (root<<1|1)
	#define mid ((l+r)>>1)
	void insert(int x,pii v,int root=1,int l=1,int r=n)
	{
		if(l==r) return t[root].val=v,void();
		if(x<=mid) insert(x,v,ls,l,mid);
		else insert(x,v,rs,mid+1,r);
		t[root].val=max(t[ls].val,t[rs].val);
	}
	void add(int x,int y,int v,int root=1,int l=1,int r=n)
	{
		if(x>y) return;
		if(l>=x&&r<=y) return t[root].tag+=v,t[root].val.fi+=v,void();
		if(x<=mid) add(x,y,v,ls,l,mid);
		if(y>mid) add(x,y,v,rs,mid+1,r);
		t[root].val=max(t[ls].val,t[rs].val);t[root].val.fi+=t[root].tag;
	}
	int query(int x,int root=1,int l=1,int r=n,int tag=0)
	{
		if(l==r) return t[root].val.fi+tag;
		tag+=t[root].tag;
		if(x<=mid) return query(x,ls,l,mid,tag);
		return query(x,rs,mid+1,r,tag);
	}
	#undef mid
}using namespace Shiki;
int f[200005][20],dfn[200005],cnt,dep[200005],siz[200005];
void dfs1(int u,int fa)
{
	f[u][0]=fa;dfn[u]=++cnt;siz[u]=1;
	for(int i=1;i<20;i++) f[u][i]=f[f[u][i-1]][i-1];
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa) continue;
		dep[v]=dep[u]+1;
		dfs1(v,u);siz[u]+=siz[v];
	}
}
inline int kfa(int x,int k){for(int i=19;~i;i--) if(k>=(1<<i)) k-=(1<<i),x=f[x][i];return x;}
int ans[200005];
int L[400005],R[400005],V[400005],top;
inline void init(){while(top) add(L[top],R[top],V[top]),--top;}
inline int lca(int x,int y)
{
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=19;~i;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=19;~i;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
inline int find(int u,int v){for(int i=19;~i;i--) if(dep[f[u][i]]>dep[v]) u=f[u][i];return u;}
inline int check(int dis,int u)
{
	for(int i=1;i<=m;i++)
	{
		if(t[1].val.fi<=dis) return init(),1;
		int v=t[1].val.se;
		if(dfn[v]>=dfn[u]&&dfn[v]<=dfn[u]+siz[u]-1)
		{
			int p=kfa(v,dis-1);
			int w=-query(dfn[p])+1;
			add(dfn[p],dfn[p]+siz[p]-1,w);
			++top;L[top]=dfn[p],R[top]=dfn[p]+siz[p]-1,V[top]=-w;
		}
		else
		{
			if(dfn[u]>=dfn[v]&&dfn[u]<=dfn[v]+siz[v]-1)
			{
				int k=dep[u]-dep[v]-dis+1;
				int p=kfa(u,k);
				int w=dep[u]-dep[p]-1;
				int x=find(u,p);
				add(1,n,-w);add(dfn[x],dfn[x]+siz[x]-1,w);
				++top;L[top]=1,R[top]=n,V[top]=w;
				++top;L[top]=dfn[x],R[top]=dfn[x]+siz[x]-1,V[top]=-w;
			}
			else
			{
				int lc=lca(u,v);
//				cout<<u<<" "<<v<<" "<<lc<<" "<<dep[3]<<" "<<dep[lc]<<" "<<dis<<endl;
				if(dep[v]-dep[lc]>dis-1) 
				{
					int p=kfa(v,dis-1);
					int w=-query(dfn[p])+1;
					add(dfn[p],dfn[p]+siz[p]-1,w);
					++top;L[top]=dfn[p],R[top]=dfn[p]+siz[p]-1,V[top]=-w;
				}
				else
				{
					int k=dis-1-dep[v]+dep[lc];
					k=dep[u]-dep[lc]-k;
					int p=kfa(u,k);
					int w=dep[u]-dep[p]-1;
					int x=find(u,p);
					add(1,n,-w);add(dfn[x],dfn[x]+siz[x]-1,w);
					++top;L[top]=1,R[top]=n,V[top]=w;
					++top;L[top]=dfn[x],R[top]=dfn[x]+siz[x]-1,V[top]=-w;
				}
			}
		}
	}
	int res=t[1].val.fi<=dis;
	init();
	return res;
}
void dfs2(int u,int fa)
{
	int l=0,r=n,res=0;
	if(fa) l=max(0,ans[fa]-1),r=min(n,ans[fa]+1);
	while(l<=r)
	{
		int mid=l+r>>1;
		if(check(mid,u)) res=mid,r=mid-1;
		else l=mid+1;
	}
	ans[u]=res;
	if(op==0) return;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(v==fa) continue;
		add(dfn[v],dfn[v]+siz[v]-1,-2);add(1,n,1);
		dfs2(v,u);
		add(dfn[v],dfn[v]+siz[v]-1,2);add(1,n,-1);
	}
}
int main()
{
//	freopen("acorn.in","r",stdin);
//	freopen("acorn.out","w",stdout);
//	read(id,T);
	T=1; 
	while(T--)
	{	
		memset(head,0,sizeof head);
		cnt_edge=0;
		read(n,m,op);
		for(int i=1;i<n;i++)
		{
			int u,v;read(u,v);
			add_edge(u,v);add_edge(v,u);
		}
		cnt=0;
		memset(dep,0,sizeof dep);
		dfs1(1,0);
		for(int i=1;i<=(n<<2);i++) t[i].val={0,0},t[i].tag=0;
		for(int i=1;i<=n;i++) insert(dfn[i],{dep[i],i});
		dfs2(1,0);
		if(op==1) for(int i=1;i<=n;i++) write(ans[i]),putch(' ');
		else write(ans[1]);
		putch('\n');
	}
	flush();
	return 0;
}