题解：CF2065F Skibidus and Slay

· · 题解

前置知识

题意

如果一个长度为 n 的序列中的众数出现次数严格大于 \lfloor\frac{n}{2}\rfloor，那么这个序列的支配度就为其众数。

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

思路

注意到：

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

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

题目只是问是否有支配度为 i 的路径，按长度为 2 和长度为 3 扫一遍即可。

实现

长度为 2 的子段考虑父节点。

长度为 3 的子段考虑相同值的结点距离是否为 2 即可。

求 lca 就行。

AC code:

#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
*/