好久没写 TJ 了，今天就写一下这个。

题意

有 $N$ 个房间，第 $i$ 房间有一条通向房间 $to_i$ 的单向路径，有 $M$ 个农民，分别在房间 $s_1,s_2,\dots,s_M$。

每个时间步，每个农民都会从他们当前所在的房间出发，沿着路径移动到下一个房间。如果 Bessie 在任何时候与任意一个农民位于同一个房间，她就会被抓住。

假设 Bessie 从某个农场 $b$ 出发。在每个时间步，她有两个选择：她可以停留在当前房间，或者移动到下一个房间。

对于每个起始房间 $b$（$1\leq b\leq N$），求如果 Bessie 从房间 $b$ 出发，她最多可以选择休息多少次。

解法

明显这个是基环树森林。

分析

这里有一个结论：先在出发点停留，然后再移动是可以到达最优答案的。

因为 Bessie 最终总会到达环上，此时只要考虑环上的情况，所以我们只要安排在出发点停留的时间即可。

你可能会疑惑，Bessie 要是在到达环的路上就被抓了呢？

可以这么想，假如 Bessie 在到达环的路上（按照我们的结论，她在出发点已经停留完了，只能选择移动）有“无敌金身”，那么到达环时，她也会和农民在一起（被抓了），所以我们只需要判断最终环上的情况。

具体怎么做呢

我们先把所有基环树找出来，令每个基环树环上的一点为根，设其为 $root_i$（第 $i$ 棵树的根），并拆掉根所指向的房间的边（只是用来计算深度，农民照样走），这样就把基环树变成了树。然后求出每个点的深度（根的深度为 $0$）。

设 $tag_{i,j}$ 为第 $i$ 棵基环树的根时刻 $j$ 时，有无农民。我们肯定无法求出所有时刻，但到后面的时刻时，发现他是以环的大小而循环的，所以我们改 $tag_{i,j}(0\leq j\leq sz_i)$ 为时刻为 $k\cdot sz_i+j$ 时（$k$ 为整数，下同）沿着路径走，是否永远不会被抓（被抓为 $1$，否则为 $0$），其中 $sz_i$ 是第 $i$ 棵基环树环的大小。

设 $dp_i$ 为农民到达 $i$ 点的最短时间，那么 Bessie 最多可以在 $i$ 点停留 $dp_i-1$ 的时间。

假如 Bessie 选择初始点 $b$ 停留 $dp_b-1$ 的时间，如果 $tag_{i,(dep_b+dp_b-1) \mod sz_i}$ 为 $0$，那么答案为 $dp_b-1$。

如果 $tag_{i,(dep_b+dp_b-1) \mod sz_i}$ 为 $1$ 呢？ 直接枚举肯定不行，预处理一个 $dis_{i,j}$ 表示第 $i$ 棵基环树，如果等了一段时间从出发点到达根时的时间为 $k\cdot sz_i+j$，想不被抓还需在出发点至少少等多少时间（时光倒流）。

这样我们答案明显是 $dp_b-1-dis_{i,(dep_b+dp_b-1) \mod sz_i}$（先等 $dp_b-1$ 的时间再时光倒流 $dis_{i,(dep_b+dp_b-1) \mod sz_i}$ 的时间）。

特殊情况

上面是没有特殊情况的，特殊情况：

• 可以等无限久。
• 一定会被抓：$dp_b-1-dis_{i,(dep_b+dp_b-1) \mod sz_i}$ 为负数。

三二一，上代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e5+100,oo=0x3f3f3f3f;
int n,m,tot;
int to[N];
vector<int> a[N];
int dp[N];
int tp[N],dep[N],vis[N],root[N],sz[N],st[N],top;
bool s[N];
vector<bool> tag[N];
vector<int> dis[N];
void dfs(int u,int root,int f){
	tp[u]=tp[root];
	dep[u]=dep[f]+1;
	if(s[u]){
		dp[u]=0;
		tag[tp[root]][dep[u]%sz[tp[root]]]=true;
	}
	else dp[u]=oo;
	for(int v:a[u]){
		if(v==root) continue;
		dfs(v,root,u);
		dp[u]=min(dp[v]+1,dp[u]);
	}
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>to[i];
		a[to[i]].push_back(i);
	}
	for(int i=1;i<=m;i++){
		int x; cin>>x;
		s[x]=true;
	}
	for(int i=1;i<=n;i++){ //找环
		if(vis[i]) continue;
		int u=i;
		while(!vis[u]){
			vis[u]=i;
			st[++top]=u;
			u=to[u];
		}
		if(vis[u]==i){
			++tot;
			root[tot]=u;
			int v=u;
			do{
				tp[v]=tot;
				sz[tot]++;
				v=st[top--];
			}while(v!=u);
			top=0;
			tag[tot].resize(sz[tot]);
		}
	}
	dep[0]=-1;
	for(int i=1;i<=tot;i++){
		dfs(root[i],root[i],0); //更新树上的 dp
		int v=to[root[i]],from=root[i];
		while(v!=root[i]){ //进一步更新环上的 dp
			dp[v]=min(dp[from]+1,dp[v]);
			from=v;
			v=to[v];
		}
	}
	for(int i=1;i<=tot;i++){ // 求 dis
		dis[i].resize(sz[i]);
		if(tag[i][0]) dis[i][0]=oo;
		else dis[i][0]=0;
		for(int j=1;j<sz[i];j++)
			if(tag[i][j]) dis[i][j]=min(oo,dis[i][j-1]+1);
			else dis[i][j]=0;
		dis[i][0]=min(dis[i][0],dis[i][sz[i]-1]+1);
		for(int j=1;j<sz[i];j++)
			if(tag[i][j]) dis[i][j]=min(oo,dis[i][j-1]+1);
			else dis[i][j]=0;
	}
	for(int i=1;i<=n;i++){
		if(dp[i]==oo) cout<<"-2\n";
		else{
			if(dis[tp[i]][(dep[i]+dp[i]-1)%sz[tp[i]]]>dp[i]-1)
				cout<<"-1\n";
			else{
				cout<<dp[i]-1-dis[tp[i]][(dep[i]+dp[i]-1)%sz[tp[i]]]<<"\n";
			}
		}
	}
	return 0;
}

这是由 AI 翻译为中文的官方题解。

(Analysis by Alex Liang)

子任务 1：

关键的观察结论是，贝茜的最佳策略是在开始无限移动之前，将所有的休息步骤全部安排在起点完成。假设存在某个时间步骤序列 $w_1, w_2, \ldots, w_k$，贝茜在这些时刻休息并且能够无限期地避开农夫们。现在，如果贝茜改为在起始农场连续休息前 $k$ 个时间步骤，她同样能够无限期地避开农夫们。这是因为，如果她在后续路径中被某个农夫抓住，那么当她选择在 $w_1, w_2, \ldots, w_k$ 这些时刻休息时，该农夫同样会抓住她。原因在于，贝茜的渐进路径是相同的，而在 $w_1, w_2, \ldots, w_k$ 时刻能够休息这一事实确保了在她起始农场的距离 $k$ 范围内没有任何农夫。

基于这一观察，我们可以针对每个起始农场进行求解：枚举贝茜花费的休息时间总量（所有这些休息都将发生在起始农场），然后模拟整个过程。我们只需要模拟额外的 $N$ 个时间步骤，因为在此之后贝茜和所有农夫都必然已经进入了循环。朴素实现的复杂度为 $O(N^4)$。

子任务 2：

子任务 2 旨在为那些思路正确但实现并非最优的解决方案给予部分分数。

完整解法：

将函数图的每个连通分量视为一个环，其中每个环上的节点都是一棵树的根，这种视角将很有帮助。具体来说，对于每个环上节点 $i$，以 $i$ 为根的树包含节点 $i$ 本身，以及所有以 $i$ 为某个后继的非环上节点。树中的所有节点都指向其根节点，即节点 $i$。

现在来求解某个连通分量。令 $t_i$ 表示农夫到达节点 $i$ 所需的最短时间。我们知道，如果贝茜从节点 $i$ 出发，她最多可以休息 $t_i - 1$ 个时间步。我们可以通过多源 BFS，或者对每棵树进行 DFS 并找出每棵子树中最近的农夫并更新环上节点的方法，来计算出 $t_i$。

将某个环上节点 $c$ 定义为 “在时刻 $t'$ 是好的”，如果贝茜在时刻 $t'$ 位于节点 $c$ 并随后无限移动下去，能够无限期地避开农夫。

现在来求解树中深度为 $d_i$ 的某个节点 $i$。我们知道，贝茜在农夫到达节点 $i$ 之前最多可以休息 $t_i - 1$ 个时间步。假设贝茜选择休息 $0 < k \le t_i - 1$ 个时间步。那么，当且仅当该树的根节点（即环上节点）在时刻 $k + d_i$ 是“好的”时，贝茜才能无限期地避开农夫。这些约束条件确保了贝茜在休息期间是安全的，并且当她开始在环上连续移动时也是安全的（这也保证了当她沿着树向上移动时，如果适用的话，不会遇到任何农夫）。

我们将问题归结为：找到最大的 $0 \le k \le t_i - 1$，使得贝茜在时刻 $k + d_i$ 到达一个“好的”环上节点。令环上节点按任意循环顺序排列为 $c_1, c_2, \ldots, c_x$，并设该树的根节点为 $c_r$。我们可以标记出哪些环上节点在时刻 $0$（任何移动开始之前）是“好的”。那么，如果 $c_{(r-(t_i-1)+d_i))\%x}$ 被标记，贝茜就能到达一个“好的”环上节点。

假设贝茜休息了全部 $t_i - 1$ 个时间步。那么，如果 $c_{(r-(t_i-1+d_i))\%x}$ 被标记，她就能够无限期地避开农夫。如果该节点未被标记，我们希望找到贝茜可以牺牲的最少等待时间，即从 $c_{(r-(t_i-1+d_i))\%x}$ 到某个被标记的环上节点的最近距离（遵循循环顺序，即在数组 $c_1, c_2, \ldots, c_x$ 上向右循环移动）。这个距离可以预先为所有环上节点计算出来。对于某个环上节点 $c_i$，设该最小距离为 $y_i$。那么，对于节点 $i$，如果不是特殊情况，其答案即为 $t_i - 1 - y_{(r-(t_i-1+d_i))\%x}$。

我们需要检查的特殊情况包括：$t_i = \infty$（贝茜可以无限休息），以及 $t_i - 1 - w_{(r-(t_i-1+d_i))\%x}$ 为负数（贝茜不可能避开农夫）。总体而言，该解法的时间复杂度为 $O(N)$。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, f;
    cin >> n >> f;

    vector<int> nxt(n + 1), hasFarmer(n + 1, 0);
    vector<vector<int>> radj(n + 1);

    for (int i = 1; i <= n; i++) {
        cin >> nxt[i];
        radj[nxt[i]].push_back(i);
    }
    for (int i = 1; i <= f; i++) {
        int s;
        cin >> s;
        hasFarmer[s] = 1;
    }

    vector<int> vis(n + 1, 0), close(n + 1, (int)1e9), ans(n + 1);

    for (int start = 1; start <= n; start++) {
        if (vis[start])
            continue;

        // Get cycle
        int cur = start;
        vector<int> cycle;

        while (vis[cur] != 2) {
            if (++vis[cur] == 2)
                cycle.push_back(cur);
            cur = nxt[cur];
        }

        // Get tree info
        int csz = cycle.size();
        vector<int> good(csz, 1), chop(csz, 1e9);
        vector<pair<int, int>> relevant;

        for (int i = 0; i < csz; i++) {
            function<void(int, int)> dfs = [&](int cur, int d){
                int pos = (i - d % csz + csz) % csz;
                vis[cur] = 1;
                relevant.push_back({cur, pos});

                if (hasFarmer[cur]) {
                    good[pos] = 0;
                    close[cur] = 0;
                }
                for (int to : radj[cur]) {
                    if (cur == cycle[i] && to == cycle[(i - 1 + csz) % csz])
                        continue;
                    dfs(to, d + 1);
                    close[cur] = min(close[cur], close[to] + 1);
                }
            };
            dfs(cycle[i], 0);
        }
        // Get distances to nearest good waiting spot
        for (int i = 2 * csz - 1; i >= 0; i--)
            chop[i % csz] = good[i % csz] ? 0 : chop[(i + 1) % csz] + 1;

        // Adjust close for cycle nodes
        for (int i = 0; i < 2 * csz - 1; i++)
            close[cycle[i % csz]] = min(close[cycle[i % csz]], close[cycle[(i - 1 + csz) % csz]] + 1);

        // Solve for each node
        for (auto [cur, st] : relevant) {
            if (close[cur] >= (int)1e8) {
                ans[cur] = -2;
                continue;
            }

            int ret = close[cur] - 1 - chop[(st - close[cur] % csz + 1 + csz) % csz];
            ans[cur] = ret >= 0 ? ret : -1;
        }
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << "\n";
}