题解：P11123 [ROIR 2024] 树根 (Day 1)
_AyachiNene · · 题解
思路：
首先考虑不换根的情况。一个显然的贪心，要让答案尽量小，那么每次肯定要使深度最深的点深度变小。容易发现，在保证答案不变的情况下，连向深度尽量小的点一定不劣。具体的，假设答案为
-
-
设
u 和v 的 lca 为p ： -
同理，可以分讨出每种情况造成的贡献，这里不再赘述。
这样复杂度是
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;
}