2022 CCPC Henan Provincial Collegiate Programming Contest

Problem

Solution

实现思路

1. 首先可以发现， 从所有的点出发，最终都会进入一个环中。所以可以构建一个 “基环森林”。
2. 把当前的这个联通块找出来，并单独存起来
3. 然后bfs拓扑排序把不在环上的点标记，剩下的就是环上的结点
4. 枚举环上的结点，搜索每一个以环上结点为根节点的子树
5. 统计大小相同的环上，不同深度的结点个数
6. 求一下前缀和，求出深度不超过d的结点有多少个
7. 然后枚举可以整除 $|a-b|$ 的环长，把深度小于 $min(a,b)$ 的结点累加到答案里面即可
8. 最后注意：环长最多有 $\sqrt{n}$ 种，有点不太准确，容易 Runtime Error
   准确的是：环长有 $2\sqrt{n}$ 种
   由 $1+2+3+...+k=k(k+1)/2\le n$ 得 $k\le 2\sqrt{n}$

Code

const int N = 1e5 + 5;
int a[N];
int vis[N], deg[N];
vector<int> v[N], node;
int hoop[500][N];unordered_map<int, int> mp;
int c[N], t;//第i中环长的长度，环长的种类数
int solve(int len)//离散化环的长度
{if (mp.count(len) == 0) c[++t] = len, mp[len] = t;return mp[len];
}void dfs(int x)
{vis[x] = 1;for (int y : v[x]){if (vis[y]) continue;node.push_back(y);dfs(y);}
}void dfs2(int x, int deep, int len) //以环上结点为根，搜索其子树
{for (int y : v[x]){if (vis[y]) continue;vis[y] = 2;//防止非环上结点与环上结点矛盾，使用 2 代表遍历过的非环结点hoop[solve(len)][deep + 1]++;dfs2(y, deep + 1, len);}
}void bfs()
{queue<int> q;for (int x : node)if (deg[x] == 1) q.push(x);int len = sz(node);//环长while (sz(q)){int x = q.front(); q.pop();vis[x] = 0;//0为非环结点, 1 为环上结点len--;for (int y : v[x])if (--deg[y] == 1) q.push(y);}for (int x : node)if (vis[x] == 1){hoop[solve(len)][0]++;dfs2(x, 0, len);}
}int main()
{IOS;int n; cin >> n;for (int i = 1, x; i <= n; i++){cin >> x;v[i].push_back(x);v[x].push_back(i);deg[x]++; deg[i]++;}for(int i = 1; i <= n; i++)if (vis[i] == 0){node.clear();node.push_back(i);dfs(i);bfs();} for (int i = 1; i <= t; i++)for (int j = 1; j < N; j++)hoop[i][j] += hoop[i][j - 1];int q; cin >> q;while (q--){ll x, y; cin >> x >> y;if (x == y) cout << n << endl;else{if (x > y) swap(x, y);int ans = 0;for (int i = 1; i <= t; i++)if ((y - x) % c[i] == 0)if (x < N) ans += hoop[i][x];else ans += hoop[i][N - 1];cout << ans << endl;}}return 0;
}