CSES 1160 Planets Queries II

題目概述

給你一張邊權皆為 11 的有向圖，每個節點的出度為 11 ，接下來有多筆詢問，每次詢問任兩點之間的最短距離。

題解

由於出度都是一，所以把圖構造出來之後，不難發現他的反圖就會是多個水母圖 (水母森林？) ，而我們如果把環都縮成一個點的話，水母森林就會變成一般的森林了，而如果詢問的兩點如果有解的話，那一定就是下面其中一種情況

  • 在同一個環上 (也就是同一棵樹上的根節點)
  • uu 不在環上 ， vv 在環上 (uu 可以一直往上爬，直到爬到根節點後，變成求兩點都在環上的距離)
  • uu 是 vv 的子孫 (uu 可以一直往上爬，直到爬到 vv 的位置)

而其他種情況都是無解的，所以我們來觀察一下該如何解決上面這幾種情況

  1. 都在同一個環上：設環上的其中一點為起點，則在找環時先預處理環上每個點和起點的距離是多少，假設 uu 到起點的距離是 aa ，而 vv 到起點的距離是 bb ，環的大小為 ss ，則他們兩點之間的距離為 a−bmod  sa-b \mod s
  2. uu不在環上，vv在環上：先用倍增法預除裡每個節點往上跳 2i2^i 後會跳到哪個點上，讓 uu 跳到跟 vv 同個高度，也就是跳到根節點後，求跳上去後的那個點和 vv 在環上的距離，然後跟前面跳的距離相加之後就是答案了
  3. uu 是 vv 的子孫：就輸出兩點在樹上深度的差值就好。

採到的雷

由於我縮點的方式可能會造成一個節點的小孩有很多個相同的節點，所以在建樹時需要去記錄這個節點和他的小孩是否已經建完了，避免重複遍歷的問題，前面一直沒發現所以卡了超久。

AC Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define pb push_back
#define endl '\n'
#define rep(i,m,n) for(int i = m;i<=n;++i)
using namespace std;
int dp[25][200001] = {};
vector<vector<int>>g, tr;
int root[200001] = {},dis[200001] = {},dis2[200001] = {},id[200001] = {},ouo[200001] = {},st[200001] = {};
int st_id = 0;
bitset<200001>in_stk,vis;
int n,m,tmp = 1;
inline void dfs(int u){
	if(in_stk[u]){
		int x = 1;
		root[id[u]] = id[u];
		while(in_stk[u]){
			ouo[id[u]]++;
			dis2[st[st_id-1]] = x++;
			id[st[st_id-1]] = id[u];
			in_stk[st[st_id-1]] = 0;
			st_id--;
		}
	}
	if(id[u])return;
	id[u] = tmp++,in_stk[u] = 1;
	st[st_id++] = u;
	dfs(g[u][0]);
	tr[id[g[u][0]]].pb(id[u]);
	if(in_stk[u]){
		in_stk[u] = 0;
		st_id--;
	}	
}
inline void dfs2(int u){			
	if(vis[u])return;
	vis[u] = 1;
	for(auto v:tr[u]){
		if(root[v])continue;
		root[v] = root[u];
		dis[v] = dis[u]+1;
		dfs2(v);
	}
}
inline void init(){
	rep(i,1,n){
		if(!id[i])dfs(i);
	}
	rep(i,1,n){
		if(root[id[i]]==id[i])dfs2(id[i]);
	}
	rep(i,1,17){
		rep(j,1,n){
			dp[i][j] = dp[i-1][dp[i-1][j]];
		}
	}
}
void solve(){
	cin>>n>>m;
	g.resize(n+1),tr.resize(n+1);
	rep(u,1,n){
		int v;
		cin>>v;
		g[u].pb(v);
		dp[0][u] = v;
	}
	{
		init();
	}
	function<int(int,int)> cal = [&](int u,int v){//u -> v
		if(u==v)return 0;
		if(id[u]==id[v]){
			int mod = ouo[id[u]];
			return ((dis2[u]-dis2[v])%mod+mod)%mod;
		}
		else if(root[id[v]]==id[v]){//v = is root
			int tmp = abs(dis[id[u]]-dis[id[v]]);
			for(int i = 18;i>=0;--i){
				if(tmp&(1<<i))u = dp[i][u];
			}
			return tmp+cal(u,v);
		}
		else{
			int tmp = abs(dis[id[u]]-dis[id[v]]);
			return tmp;
		}
	};
	auto f = [&](int u,int v){
		if(dis[id[u]]<dis[id[v]])swap(u,v);
		int tmp = dis[id[u]]-dis[id[v]];
		for(int i = 17;i>=0;--i){
			if(tmp&(1<<i))u = dp[i][u];
		}
		return u==v;
	};
	while(m--){
		int u,v;
		cin>>u>>v;
		if(root[id[u]]!=id[u] and root[id[v]]!=id[v] and dis[id[u]]<dis[id[v]]){
			cout<<-1<<endl;
		}
		else if(root[id[u]]!=root[id[v]]){
			cout<<-1<<endl;
		}
		else if(root[id[u]]!=id[u] and root[id[v]]!=id[v] and !f(u,v)){
			cout<<-1<<endl;
		}
		else if(root[id[u]]==id[u] and root[id[v]]!=id[v]){
			cout<<-1<<endl;
		}
		else{
			cout<<cal(u,v)<<endl;
		}
	}
	
}
signed main(){
	IOS;
	solve();
}