$ZZQ$ 是一国之主。 这个国家有$N$个城市， 第$i$个城市与第$(i + 1) (mod N)$和$(i - 1) (mod N)$在一个正$N$边形相连。
$ZZQ$ 又新建了$N - 3$条道路。这些道路都是连接两个城市的直线 段，且任意两条线段都只可能在城市处相交，不会在旧的道路上新建 道路。同时$ZZQ$钦定任何一条新旧道路通行都只需要花费$1$天时间。
建设完成后，$ZZQ$开始了$M$次旅行，她想知道每次旅行最少需要 花费多少天。
输入格式：
第一行输入 一个 个正整数$N$，表示城市个数。
接下来$N - 3$行，每行两个整数$u, v$，表示这条道路连接的两个城市。
接下来一个整数$M$，表示旅行次数。
接下来$M$行，每行两个整数$u, v$表示这次旅行的起点和终点。
保证起点和终点不同。
输出格式：
对于每个询问，输出一行一个整数$ans$表示答案。
其实这题在$BZOJ$上有原题：$BZOJ - 4449$
首先这显然是一个平面图，然后正解是平面图转对偶图 + 点分治，对偶图是什么？我不知道啊。
然后对偶图就是将平面图的面看作点，然后相邻的面之间连边，其中有$N - 3$条边，$N - 2$个点，故对偶图显然是一棵树。
其中，要建对偶图的话，每次选择$Deg$为$2$的点，再处理一下三角剖分，就能知道有哪些面相连了。
然后就在树上点分治。
至于过程，考虑一条原图的新加的边，如果某个询问的两个点恰好跨过它，那么就一遍$BFS$就好了，否则找到它们所在的被此时直线切割形成的两个块的左块或右块进行分治，于是可以使用点分治。
那么如何处理多个询问有哪几个横跨了当前点分治中心呢？只需将询问编号与当前分治中心用链式前向星连起来，访问到当前中心时扫一遍即可，当然这是需要下穿的。
复杂度$O(NlogN)$。
代码：
1 #pragma GCC optimize ("O3") 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 #include <vector> 6 #include <queue> 7 #include <algorithm> 8 9 using namespace std; 10 11 const int MAXN = 1e05 + 10; 12 const int MAXM = 1e05 + 10; 13 const int MAXQ = 1e05 + 10; 14 15 const int INF = 0x7fffffff; 16 17 struct LinkedForwardStar { 18 int to; 19 bool ban; 20 21 int next; 22 } ; 23 24 LinkedForwardStar Link[MAXM << 1]; 25 int Head[MAXN]= {0}; 26 int size = 1; 27 28 void Insert (int u, int v) { 29 Link[++ size].to = v; 30 Link[size].ban = false; 31 Link[size].next = Head[u]; 32 33 Head[u] = size; 34 } 35 36 vector<int> Graph[MAXN]; 37 38 struct Edge { 39 int u, v; 40 int index; 41 42 Edge () {} 43 44 Edge (int fu, int fv, int find) : 45 u (fu), v (fv), index (find) {} 46 47 bool operator < (const Edge& p) const { 48 if (u == p.u) 49 return v < p.v; 50 return u < p.u; 51 } 52 } ; 53 54 Edge Edges[MAXN * 3]; 55 int edges = 0; 56 int ind = 0; 57 58 int Triangle[MAXN][3]; 59 60 void AddEdge (int x, int y, int z) { // 处理三角剖分 61 ind ++; 62 Triangle[ind][0] = x; 63 Triangle[ind][1] = y; 64 Triangle[ind][2] = z; 65 Edges[++ edges] = Edge (min (x, y), max (x, y), ind); 66 Edges[++ edges] = Edge (min (x, z), max (x, z), ind); 67 Edges[++ edges] = Edge (min (y, z), max (y, z), ind); 68 // cout << "Test: " << x << ‘ ‘ << y << ‘ ‘ << z << endl; 69 } 70 71 int N, M; 72 73 int Deg[MAXN]= {0}; 74 bool Vis[MAXN]= {false}; 75 76 queue<int> Que; 77 78 void Toposort () { 79 for (int i = 1; i <= N; i ++) 80 if (Deg[i] == 2) 81 Que.push(i); 82 83 while (! Que.empty()) { 84 int u = Que.front(); 85 Que.pop(); 86 87 if (Deg[u] != 2) 88 continue; 89 Vis[u] = true; 90 91 int x = 0, y; 92 for (int i = 0; i < (int) Graph[u].size(); i ++) { 93 int v = Graph[u][i]; 94 if (Vis[v]) 95 continue; 96 97 ! x ? x = v : y = v; 98 Deg[v] --; 99 if (Deg[v] == 2) 100 Que.push(v); 101 } 102 AddEdge (u, x, y); 103 } 104 } 105 106 void Construct () { 107 sort (Edges + 1, Edges + edges + 1); 108 for (int i = 1; i < edges; i ++) 109 if (Edges[i].u == Edges[i + 1].u && Edges[i].v == Edges[i + 1].v) { 110 Insert (Edges[i].index, Edges[i + 1].index); 111 Insert (Edges[i + 1].index, Edges[i].index); 112 } 113 } 114 115 int Size[MAXN]= {0}; 116 117 int tot; 118 119 int minval = INF, gravity; 120 void Get_Gravity (int root, int father) { 121 Size[root] = 1; 122 int maxpart = 0; 123 for (int i = Head[root]; i; i = Link[i].next) { 124 int v = Link[i].to; 125 if (v == father || Link[i].ban) 126 continue; 127 128 Get_Gravity (v, root); 129 Size[root] += Size[v]; 130 maxpart = max (maxpart, Size[v]); 131 } 132 maxpart = max (maxpart, tot - Size[root]); 133 134 if (maxpart < minval) { 135 minval = maxpart; 136 gravity = root; 137 } 138 } 139 140 LinkedForwardStar Qlink[MAXQ << 5]; 141 int Qhead[MAXN]; 142 int qsize = 0; 143 144 void Qinsert (int u, int v) { 145 Qlink[++ qsize].to = v; 146 Qlink[qsize].next = Qhead[u]; 147 148 Qhead[u] = qsize; 149 } 150 151 int Answer[MAXQ]= {0}; 152 153 int Dist[3][MAXN]= {0}; 154 155 int cur = 0; 156 157 int Rec[MAXN * 3]; 158 int Belong[MAXN], Last[MAXN]; 159 // Belong[]记录所属子树，Last[]记录分治中心编号（为了防止BFS越过当前分支中心管理子树） 160 161 int cnt = 0; 162 163 void BFS (int S, int type) { 164 while (! Que.empty()) 165 Que.pop(); 166 for (int i = 1; i <= cnt; i ++) 167 Dist[type][Rec[i]] = INF; 168 169 Que.push(S); 170 Dist[type][S] = 0; 171 172 while (! Que.empty()) { 173 int u = Que.front(); 174 Que.pop(); 175 176 for (int i = 0; i < (int) Graph[u].size(); i ++) { 177 int v = Graph[u][i]; 178 if (Dist[type][v] < INF || Last[v] < cur) 179 continue; 180 181 Dist[type][v] = Dist[type][u] + 1; 182 Que.push(v); 183 } 184 } 185 } 186 187 void DFS (int root, int father, int top) { 188 for (int j = 0; j < 3; j ++) { 189 Rec[++ cnt] = Triangle[root][j]; 190 Belong[Triangle[root][j]] = top; 191 Last[Triangle[root][j]] = cur; 192 } 193 194 for (int i = Head[root]; i; i = Link[i].next) { 195 int v = Link[i].to; 196 if (v == father || Link[i].ban) 197 continue; 198 DFS (v, root, top); 199 } 200 } 201 202 pair<int, int> Queries[MAXQ]; 203 204 int Query[MAXQ]; 205 206 void Solve (int root) { 207 if (! Qhead[root]) 208 return ; 209 210 tot = Size[root]; 211 minval = INF; 212 Get_Gravity (root, 0); 213 cur ++, cnt = 0; 214 for (int i = Head[gravity]; i; i = Link[i].next) { 215 int v = Link[i].to; 216 if (Link[i].ban) 217 continue; 218 DFS (v, gravity, v); 219 } 220 for (int j = 0; j < 3; j ++) { 221 Rec[++ cnt] = Triangle[gravity][j]; 222 Belong[Triangle[gravity][j]] = gravity; 223 Last[Triangle[gravity][j]] = cur; 224 } 225 226 for (int j = 0; j < 3; j ++) 227 BFS (Triangle[gravity][j], j); 228 cnt = 0; 229 for (int i = Qhead[root]; i; i = Qlink[i].next) { 230 int v = Qlink[i].to; 231 Query[++ cnt] = v; 232 } 233 Qhead[root] = 0; 234 235 for (int i = 1; i <= cnt; i ++) { 236 int u = Queries[Query[i]].first, v = Queries[Query[i]].second; 237 if (Belong[u] == Belong[v]) { 238 if (Belong[u] == gravity) 239 Answer[Query[i]] = 1; // 在同一个三角剖分中 240 else 241 Qinsert (Belong[u], Query[i]); 242 } 243 else { 244 for (int j = 0; j < 3; j ++) 245 Answer[Query[i]] = min (Answer[Query[i]], Dist[j][u] + Dist[j][v]); 246 } 247 } 248 249 for (int i = Head[gravity]; i; i = Link[i].next) { 250 int v = Link[i].to; 251 if (! Link[i].ban) { 252 Link[i ^ 1].ban = true; 253 Solve (v); 254 } 255 } 256 } 257 258 int getnum () { 259 int num = 0; 260 char ch = getchar (); 261 262 while (! isdigit (ch)) 263 ch = getchar (); 264 while (isdigit (ch)) 265 num = (num << 3) + (num << 1) + ch - ‘0‘, ch = getchar (); 266 267 return num; 268 } 269 270 int main () { 271 // freopen ("city.in", "r", stdin); 272 273 N = getnum (); 274 275 for (int i = 1; i <= N; i ++) 276 Dist[0][i] = Dist[1][i] = Dist[2][i] = INF; 277 278 for (int i = 1; i < N; i ++) { 279 Graph[i].push_back(i + 1); 280 Graph[i + 1].push_back(i); 281 Deg[i] ++, Deg[i + 1] ++; 282 } 283 Graph[1].push_back(N), Graph[N].push_back(1); 284 Deg[1] ++, Deg[N] ++; 285 for (int i = 1; i <= N - 3; i ++) { 286 int u, v; 287 u = getnum (), v = getnum (); 288 u ++, v ++; 289 Graph[u].push_back(v); 290 Graph[v].push_back(u); 291 Deg[u] ++, Deg[v] ++; 292 } 293 294 Toposort (); 295 Construct (); 296 297 M = getnum (); 298 299 for (int i = 1; i <= M; i ++) { 300 int u, v; 301 u = getnum (), v = getnum (); 302 u ++, v ++; 303 if (u != v) { 304 Queries[i] = make_pair (u, v); 305 Qinsert (1, i); // 一开始所有询问都位于根节点的子树中 306 Answer[i] = INF; 307 } 308 } 309 310 Size[1] = N; 311 Solve (1); 312 313 for (int i = 1; i <= M; i ++) 314 printf ("%d\n", Answer[i]); 315 316 return 0; 317 } 318 319 /* 320 6 321 0 2 322 0 3 323 0 4 324 4 325 1 5 326 3 0 327 4 5 328 2 4 329 */
原文：https://www.cnblogs.com/Colythme/p/9874001.html
