CF983E NN country 題解

2023-08-17 02:07 作者:泉五第一深情 0人讀過 | 我要投稿

題意

給定一棵樹和若干條路線，每條路線相當(dāng)于 $a%2Cb$ ?之間的路徑，途徑路徑上的每個(gè)點(diǎn)。

給出若干個(gè)詢問，每次詢問從 $x$ ?到 $y$ ?至少需要利用幾條路線。

Solution

考慮子問題，兩個(gè)詢問點(diǎn)在同一條鏈上，這樣問題就類似 [SCOI2015] 國(guó)旗計(jì)劃，只不過這道題是環(huán)上問題，但思路相同。

對(duì)于鏈，考慮貪心，對(duì)于每一個(gè)點(diǎn) $to_i%E2%80%8B$ ?跳到能到達(dá)的最遠(yuǎn)的點(diǎn)?，容易想到下一步應(yīng)當(dāng)是跳到 $to_%7Bto_i%7D$ ，故考慮倍增優(yōu)化這個(gè)不斷往前跳的過程。定義 $jump_%7Bi%2Ck%7D$ ?為點(diǎn) i 跳 $2%5Ek$ ?步能到達(dá)的最遠(yuǎn)節(jié)點(diǎn)，可以用 $%5Cmathcal%7BO%7D(n%5Clog%20n)$ ?復(fù)雜度的時(shí)間來處理出? $%20jump%20$ 數(shù)組。

考慮樹上的兩個(gè)點(diǎn)，對(duì)于 $x$ ?是? $y$ ?的祖先節(jié)點(diǎn)（ $y$ ?為 $x$ ?祖先節(jié)點(diǎn)時(shí)同理）的情況，同鏈上情況處理。

對(duì)于兩個(gè)點(diǎn)分別不是對(duì)方父親節(jié)點(diǎn)的情況，考慮將問題拆分為? $x$ ?到? $lca$ ?和? $y$ ?到 $lca$ ?兩個(gè)問題處理。令 $ans_x%20$ 為? $x$ ?跳到 $lca$ ?的最小步數(shù)， $ans_y$ ?為? $y$ 跳到 $lca$ ?的最小步數(shù)， $pre_x$ ?為? $x$ 向上跳 $ans_x-1$ ?步到達(dá)的深度最淺的節(jié)點(diǎn)，即跳到 $lca$ ?的前一個(gè)節(jié)點(diǎn)，同理。考慮兩種情況：

有一條路線同時(shí)經(jīng)過? $pre_x$ ?和 $pre_y$ ；
不存在一條路線同時(shí)經(jīng)過 $pre_x$ ?和 $pre_y$ 。

對(duì)于第二種情況，答案即為，對(duì)于第一種情況，答案為 $ans_x%2Bans_y-1$ 。問題轉(zhuǎn)化為如何維護(hù)是否存在一條路線經(jīng)過兩個(gè)點(diǎn)。

發(fā)現(xiàn)對(duì)于一個(gè)節(jié)點(diǎn) $u$ ，只要 $u$ 的子樹中存在一個(gè)點(diǎn)，使得存在一條從其出發(fā)的路徑在 $v$ 的子樹中結(jié)束，則存在一條路徑同時(shí)經(jīng)過 $u$ 和 $v$ 。考慮通過 dfs 序轉(zhuǎn)化為區(qū)間問題，令 $size_i$ ?為節(jié)點(diǎn) $i$ ?的子樹大小，則問題進(jìn)一步轉(zhuǎn)化為詢問是否存在一條路徑 $(fr%2Cto)$ ?使得 $dfn_%7Bfr%7D%5Cin%5Bdfn_x%2Cdfn_x%2Bsize_x-1%5D%20%EF%BC%8Cdfn_%7Bto%7D%5Cin%5Bdfn_y%2Cdfn_y%2Bsize_y-1%5D$ 。考慮二維數(shù)點(diǎn)，即查詢平面上矩形 $%5B(dfn_x%2Cdfn_y)%2C(dfn_x%2Bsize_x-1%2Cdfn_y%2Bsize_y-1)%5D$ ?是否有點(diǎn)。將詢問離線排序并用樹狀數(shù)組維護(hù)即可。