Solution

记录我思考的过程，。

先考虑 Bob 的策略。显然，他只会让自己的卡片朝向 Alice 的卡片移动，而且一定会这么做。

Alice 的策略为：选定一条链

u \to v

，将卡片放在

u

上。先不断向

v

移动。到达

v

之后，她会选择停在

v

不动，等着 Bob 来。

这样需要满足：

对于链上任何一点 $w$ 和任何一个 Bob 起始点 $s$ ，都有 $\text{dis}(u,w) < \text{dis}(s,w)$ ；
最大化 $\min_i \text{dis}(s_i,v)$ 。

显然对于每个

v

，都可以算出

t_v=\min_{i} \text{dis}(s_i,v)

的值。

那么问题转化为：给定

u

，找到满足下列要求的

v

对应的

t_v

的最大值——

u

到

v

路径上所有点

p

的

t_p

都大于

\text{dis}(u,p)

。

关键性质：下面证明，路径

(u,v)

上任何一个点

p

满足

t_p > \text{dis}(u,p)

，等价于

t_v > \text{dis}(u,v)

。其实是显然的，因为我们将

p

从

u

往

v

移动时，

t_v

最多增加

1

，而

\text{dis}(u,v)

会减少

1

，即

t_v - \text{dis}(u,v)

在减小。这样已经可以用一些分块乱做了，能做到

O(n \sqrt{n \log n})

，不清楚能不能过。

大规模点对统计考虑点分治。每个点显然会对

dep_u \le k

的所有点产生贡献（不在同一子树内毫无影响，这样会更劣）。直接前缀和即可，复杂度

O(n \log n)

。

这是代码：

CPP

#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=2e5+10;
int n,k,flg[MAXN],t[MAXN],ans[MAXN],din[MAXN],dout[MAXN],pre[MAXN];
vector<int> G[MAXN];
void dfs1(int u,int f) {for(auto v:G[u]) if(v!=f) dfs1(v,u),din[u]=min(din[u],din[v]+1);return ;}
void dfs2(int u,int f) {for(auto v:G[u]) if(v!=f) dout[v]=min(din[u],dout[u])+1,dfs2(v,u);return ;}
int cut[MAXN],dep[MAXN],sze[MAXN],mx[MAXN],mdep;
void dfs(int u,int f) {
	sze[u]=1,mx[u]=0;
	for(auto v:G[u]) if(v!=f&&!cut[v]) dfs(v,u),sze[u]+=sze[v],mx[u]=max(mx[u],sze[v]);
	return ;	
}
int find_core(int u,int f,int al) {
	if(max(mx[u],al-sze[u])<=al/2) return u;
	for(auto v:G[u]) if(v!=f&&!cut[v]) {
		int ans=find_core(v,u,al);
		if(ans!=-1) return ans;
	}
	return -1;
}
void get_dep(int u,int f,int& md) {
	if(f) dep[u]=dep[f]+1;
	else dep[u]=0;
	md=max(md,dep[u]+1);
	for(auto v:G[u]) if(v!=f&&!cut[v]) get_dep(v,u,md);
	return ;	
}
void add_imp(int u,int f) {
	if(t[u]-dep[u]-1>=0) pre[min(mdep,t[u]-dep[u]-1)]=max(pre[min(mdep,t[u]-dep[u]-1)],t[u]);
	for(auto v:G[u]) if(v!=f&&!cut[v]) add_imp(v,u);
	return ;
}
void add_ans(int u,int f) {
	ans[u]=max(ans[u],pre[dep[u]]);
	for(auto v:G[u]) if(v!=f&&!cut[v]) add_ans(v,u);
	return ;	
}
void solve(int u) {
	dfs(u,0),u=find_core(u,0,sze[u]);
	mdep=0,get_dep(u,0,mdep);
	ffor(i,0,mdep) pre[i]=-0x3f3f3f3f3f3f3f3f;
	add_imp(u,0);roff(i,mdep-1,0) pre[i]=max(pre[i],pre[i+1]);add_ans(u,0);
	cut[u]=1;for(auto v:G[u]) if(!cut[v]) solve(v);
	return ;
}
int main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n;
	ffor(i,1,n-1) {int u,v;cin>>u>>v,G[u].push_back(v),G[v].push_back(u);}
	cin>>k;
	memset(din,0x3f,sizeof(din)),memset(dout,0x3f,sizeof(dout));
	ffor(i,1,k) {int id;cin>>id,flg[id]=1,din[id]=dout[id]=0;}
	dfs1(1,0),dfs2(1,0);
	ffor(i,1,n) t[i]=min(din[i],dout[i]);
	solve(1);
	ffor(i,1,n) cout<<ans[i]<<' ';
	return 0;
}

题解：CF1452G Game On Tree

文章操作

Solution

相关推荐

评论

题解：CF1452G Game On Tree