专栏文章

【题解】P11123 [ROIR 2024] 树根 (Day 1)

zzhouxianzhuo
P11123题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@min749b7
此快照首次捕获于
2025/12/01 21:39
3 个月前
此快照最后确认于
2025/12/01 21:39
3 个月前
查看原文
考虑二分答案，思考如何判断一个答案是否可行。
假设当前需判断答案为 limlim 是否可行。贪心的想，可以每次找到整棵树内最深的点 xx，从根向 xx 的 lim−1lim-1 级祖先 yy 连边，这样整棵 yy 的子树就都合法了，可以删掉这棵子树。
如此重复 kk 次后，判最深的点的深度是否小于等于 limlim，即可判断答案为 limlim 是否可行。
查找整棵树内最深的点可以用线段树维护，而删去一棵子树相当于区间减 nn，因为不存在点的深度超过 nn，由此得判断一次的复杂度为 O(klog⁡n)O(k\log n)。
接下来考虑相邻点换根对深度、树上 kk 级祖先、子树的影响，设换根后的根为 rtrt。
  • 换根后的深度是容易维护的，则只需将 rtrt 的子树减 11，其它点加 11 即可。
  • 对于点 xx，树上 kk 级祖先需要分讨：
    设 ll 为原树上 rtrt 和 xx 的 lcalca。
    • 若 dis(l,x)≥kdis(l,x)\ge k，则 xx 的树上 kk 级祖先为原树上 xx 的树上 kk 级祖先。
    • 否则，xx 的树上 kk 级祖先为原树上 rtrt 的 dis(rt,x)−kdis(rt,x)-k 级祖先。
  • 对于点 xx，子树亦需分讨：
    • 若 rt=xrt=x，则 xx 的子树为所有点。
    • 若在原树中，rtrt 在 xx 的子树内，设 yy 为 xx 向 rtrt 方向的儿子，则此时 xx 的子树为除原树中 yy 的子树外的所有点。
    • 否则，xx 的子树不变。
对于每个点都二分答案可以做到 O(nklog⁡2n)O(nk\log^2n)，但还能更优。
发现换根后的答案变动不超过 11，因此换根时的判断次数可以缩至 O(1)O(1)，这样做的复杂度为 O(klog⁡2n+nklog⁡n)O(k\log^2 n+nk\log n)。
代码如下，具体看注释：
CPP
#include<bits/stdc++.h>
using namespace std;
struct opt{
	int l,r,v;
};
int n,k,t,son[200010],ans[200010];
int hd[200010],ne[400010],to[400010],tot;
int dp[200010],cnt,dfn[200010],rnk[200010],btm[200010],st[200010][25],lg[200010],jump[200010][25];
long long tag[800010];
pair<long long,int> tree[800010];
vector<opt> op;
void add(int x,int y){
	tot+=1;
	ne[tot]=hd[x];
	hd[x]=tot;
	to[tot]=y;
}
void dfs(int x,int fa){
	dp[x]=dp[fa]+1;
	cnt+=1;
	dfn[x]=cnt;
	rnk[cnt]=x;
	st[dfn[x]][0]=dfn[fa];
	jump[x][0]=fa;
	for(int i=1;i<=20;i++)
		jump[x][i]=jump[jump[x][i-1]][i-1];
	for(int i=hd[x];i>=1;i=ne[i])
	{
		if(to[i]==fa)continue;
		dfs(to[i],x);
	}
	btm[x]=cnt;
}
void init(){
	for(int i=2;i<=n;i++)
		lg[i]=lg[i>>1]+1;
	for(int j=1;j<=20;j++)
	{
		for(int i=1;i+(1<<j)-1<=n;i++)
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
	}
}
//预处理 st 表 
inline int ask(int l,int r){
	return min(st[l][lg[r-l+1]],st[r-(1<<lg[r-l+1])+1][lg[r-l+1]]);
}
inline int lca(int x,int y){
	if(x==y)return x;
	if(dfn[x]>dfn[y])swap(x,y);
	return rnk[ask(dfn[x]+1,dfn[y])];
}
//st 表求原树中 x 和 y 的 lca 
inline int dis(int x,int y){
	return dp[x]+dp[y]-dp[lca(x,y)]*2;
}
//x 到 y 的距离 
int up(int x,int k){
	for(int i=0;i<=20;i++)
		if(k&(1<<i))x=jump[x][i];
	return x;
}
//原树中 x 的 k 级祖先 
int anc(int rt,int x,int k){
	if(dis(rt,x)<=k)return rt;
	int l=lca(rt,x);
	if(dis(l,x)>=k)return up(x,k);
	//树上 k 级祖先分讨 1 
	return up(rt,dis(rt,x)-k);
	//树上 k 级祖先分讨 2 
}
//根为 rt 时 x 的 k 级祖先 
inline void pushup(int x){
	tree[x]=max(tree[x*2],tree[x*2+1]);
}
inline void addtag(int x,long long v){
	tree[x].first+=v;
	tag[x]+=v;
}
inline void pushdown(int x){
	addtag(x*2,tag[x]);
	addtag(x*2+1,tag[x]);
	tag[x]=0;
}
void build(int l,int r,int x){
	if(l==r)
	{
		tree[x]={dp[rnk[l]]-1,rnk[l]};
		return;
	}
	int mid=(l+r)>>1;
	build(l,mid,x*2);
	build(mid+1,r,x*2+1);
	pushup(x);
}
void change(int l,int r,int x,int ll,int rr,int v){
	if(l>=ll&&r<=rr)
	{
		addtag(x,v);
		return;
	}
	pushdown(x);
	int mid=(l+r)>>1;
	if(ll<=mid)change(l,mid,x*2,ll,rr,v);
	if(rr>mid)change(mid+1,r,x*2+1,ll,rr,v);
	pushup(x);
}
//线段树维护整棵树深度最深的点 
bool check(int rt,int lim){
	int ts=k;
	while(ts>=1)
	{
		ts-=1;
		int x=tree[1].second;
		//x 为整棵树最深的点 
		int y=anc(rt,x,lim-1);
		//y 为 x 的 lim-1 级祖先 
		if(y==rt)return true;
		//子树分讨 1 
		if(son[y]==0)
		{
			change(1,n,1,dfn[y],btm[y],-n);
			op.push_back((opt){dfn[y],btm[y],-n});
		}
		//子树分讨 3 
		else
		{
			change(1,n,1,1,n,-n);
			change(1,n,1,dfn[son[y]],btm[son[y]],n);
			op.push_back((opt){1,n,-n});
			op.push_back((opt){dfn[son[y]],btm[son[y]],n});
		}
		//子树分讨 2 
	}
	if(tree[1].first<=lim)return true;
	return false;
}
void clear(){
	for(opt o:op)
		change(1,n,1,o.l,o.r,-o.v);
	op.clear();
}
//消除 check 对线段树的影响 
void dfs_ans(int x,int fa){
	int l,r;
	if(x==1)
	{
		l=0;
		r=n;
	}
	//当前根为 1 则进行 O(log n) 次二分 
	else
	{
		l=max(ans[fa]-2,0);
		r=ans[fa]+1;
	}
	//当前根不为 1 则由父亲的答案进行 O(1) 次二分 
	while(l+1<r)
	{
		int mid=(l+r)>>1;
		if(check(x,mid))r=mid;
		else l=mid;
		clear();
	}
	ans[x]=r;
	for(int i=hd[x];i>=1;i=ne[i])
	{
		if(to[i]==fa)continue;
		son[x]=to[i];
		//记录向 rt 方向的儿子 
		change(1,n,1,1,n,1);
		change(1,n,1,dfn[to[i]],btm[to[i]],-2);
		//换根对深度的影响 
		dfs_ans(to[i],x);
		change(1,n,1,1,n,-1);
		change(1,n,1,dfn[to[i]],btm[to[i]],2);
		//消除换根对深度的影响 
	}
	son[x]=0;
}
int main(){
	scanf("%d%d%d",&n,&k,&t);
	for(int i=1;i<=n-1;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dfs(1,0);
	init();
	build(1,n,1);
	dfs_ans(1,0);
	if(t==0)printf("%d",ans[1]);
	else
	{
		for(int i=1;i<=n;i++)
			printf("%d ",ans[i]);
	}
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...