题解：P17406 【MX-X31-T2】「FAOI-R14」警察抓小偷

· · 题解

\texttt{sto ljx orz}

什么数数+DS 场。

显然原图为内向基环树，考虑一个叶子，显然初始时上面一定要有一个警察。

足够长时间后，小偷一定在环上，如果环上有一个点没有警察，小偷初始时一定可以选择一个位置使自己一直不被抓住。因此环上的每个点都至少要有一个警察。

一个简单的做法是：直接用倍增求出每个点顺着出边走 2^{20} 步所达的位置，以此将点集分为若干等价类，则初始时每个等价类都必须有一个警察。除去叶子的警察，剩下一定选代价最小的。

代价为 0 的警察可以多放，需要仔细讨论，具体见代码。

::::success[赛时代码]

#include<bits/stdc++.h>
#define N 1000005
#define mod 998244353
using namespace std;
long long t,n,c,s,r,m,i,j,d[N],w[N],a[N][21];
bool f[N];
vector<long long>v[N];
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>t;
    while(t--){
        cin>>n;
        c=0;
        for(i=1;i<=n;i++){
            d[i]=f[i]=0;
            v[i].clear();
        }
        for(i=1;i<=n;i++)cin>>w[i];
        for(i=1;i<=n;i++){
            cin>>a[i][0];
            d[a[i][0]]++;
        }
        for(i=1;i<=20;i++)for(j=1;j<=n;j++)a[j][i]=a[a[j][i-1]][i-1];
        for(i=1;i<=n;i++){
            if(d[i])v[a[i][20]].push_back(w[i]);
            else{
                c+=w[i];
                f[a[i][20]]=1;
            }
        }
        for(r=i=1;i<=n;i++){
            if(!v[i].empty()){
                m=LLONG_MAX;
                for(auto j:v[i])m=min(m,j);
                if(!f[i])c+=m;
                if(m){
                    if(f[i])continue;
                    s=0;
                    for(auto j:v[i])if(j==m)s++;
                    r=r*s%mod;
                }else{
                    s=1;
                    for(auto j:v[i])if(!j)s=s*2%mod;
                    r=r*(s+mod-!f[i])%mod;
                }
            }
        }
        cout<<c<<' '<<r<<'\n';
    }
}

::::