题解：CF2065F Skibidus and Slay

son_son · 2025-02-12 11:05:23 · 题解

思路

首先能想到一个暴力搜，对每一个点都跑一遍全图，但复杂度肯定是不允许的。

接着，注意到其实对于每个点只用往下跑三步。小蒟蒻太菜，只能给一个感性证明：若当前点是在三步以后才符合了答案，那么从第三个步开始跑也一定能成功。

但是如果还是 dfs 的话，即使用了上述的剪枝，菊花图的复杂度仍是不下来的。

所以可以考虑给每一个点开一个 map，记录它能连的点的点权，这样对于每个点，只需要搜它的出边，接着看那个点是否连过一个与当前点相同点权的点就做完了。

AC code:

#include<bits/stdc++.h>
using namespace std;
int _,n;
vector<int>poi[500005];
int dq[500005],ans[500005];
map<int,int>mp[500005];
int main(){
    scanf("%d",&_);
    while(_--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)mp[i].clear();
        for(int i=0;i<=n;i++){
            poi[i].clear();
            if(i!=0)scanf("%d",&dq[i]);
            ans[i]=0;
        }
        for(int i=1;i<n;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            poi[a].push_back(b);
            poi[b].push_back(a);
            mp[a][dq[b]]++,mp[b][dq[a]]++;
        }
        for(int i=1;i<=n;i++){
            if(ans[dq[i]]==1)continue;
            if(mp[i][dq[i]]){
                ans[dq[i]]=1;
                continue;
            }
            for(int j=0;j<poi[i].size();j++){
                long long nv=poi[i][j];
                if(mp[nv][dq[i]]>1){
                    ans[dq[i]]=1;
                    break;
                }
            }
        }
        for(int i=1;i<=n;i++){
            printf("%d",ans[i]);
        }
        printf("\n");
    }
}