题解：CF2065F Skibidus and Slay

前置知识

树
lca
数学

题意

如果一个长度为

n

的序列中的众数出现次数严格大于

\lfloor\frac{n}{2}\rfloor

，那么这个序列的支配度就为其众数。

问

1\sim n

中每一个值在树上是否存在一条链满足其支配度正好为当前值。

思路

注意到：

如果一个序列存在支配度，那么一定有两种情况之一出现：

存在长为 $2$ 的子段，支配度和原序列相同。
存在长为 $3$ 的子段，支配度和原序列相同。

证明很简单，考虑反证法，如果两个都不存在，那就不存在支配度。

题目只是问是否有支配度为

i

的路径，按长度为

2

和长度为

3

扫一遍即可。

实现

长度为

2

的子段考虑父节点。

长度为

3

的子段考虑相同值的结点距离是否为

2

即可。

求 lca 就行。

AC code:

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+5;
int n,a[N];
vector<int>mp[N];
vector<int>as[N];
int fa[N],det[N],son[N];
int si[N],top[N],id[N],cnt;
inline void dfs1(int p,int f){
	fa[p]=f;det[p]=det[f]+1;si[p]=1;
	int dmax=0;
	for(auto v:mp[p]){
		if(v==f)continue;
		dfs1(v,p);si[p]+=si[v];
		if(dmax<si[v])son[p]=v,dmax=si[v];
	}
}
inline void dfs2(int p,int tp){
	top[p]=tp;id[p]=++cnt;
	if(!son[p])return ;
	dfs2(son[p],tp); 
	for(auto v:mp[p]){
		if(v==son[p]||v==fa[p])continue;
		dfs2(v,v);
	}
}
inline int lca(int x,int y){
	while(top[x]!=top[y]){
		if(det[top[x]]<=det[top[y]])swap(x,y);
		x=fa[top[x]];
	}
	if(det[x]>det[y])swap(x,y);
	return x;
}
bool ans[N];
inline void solve(){
	for(int i=1;i<=n;i++)mp[i].clear(),as[i].clear(),son[i]=0,ans[i]=0;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i],as[a[i]].push_back(i);
	for(int i=1;i<n;i++){
		int x,y;cin>>x>>y;
		mp[x].push_back(y);
		mp[y].push_back(x);
	}
	dfs1(1,0);dfs2(1,1);
	for(int i=2;i<=n;i++){
		if(a[i]==a[fa[i]])ans[a[i]]=1;
	}
	for(int i=1;i<=n;i++){
		if(ans[i])continue;
		for(auto v:as[i]){
			if(ans[i])break;
			for(auto u:as[i]){
				if(v==u)continue;
				if(ans[i])break;
				if(det[u]+det[v]-2*det[lca(u,v)]==2)ans[i]=1;
			}
		}
	}
	for(int i=1;i<=n;i++)cout<<ans[i];
	cout<<'\n';
}
int main (){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--)solve();
	return 0;
}
/*
1
13
1 4 4 7 4 7 1 1 7 11 11 11 11
1 2
2 3
3 4
4 5
4 6
2 7
7 8
2 9
6 10
5 11
11 12
10 13
*/

题解：CF2065F Skibidus and Slay

文章操作

前置知识

题意

思路

实现

AC code:

相关推荐

评论

题解：CF2065F Skibidus and Slay