意味
最新の共通祖先。lca (最低共通祖先) と呼ばれます。 2 つのノードの最も近い共通祖先は、これら 2 つの点の共通祖先間の距離です。ルートノードが最も遠いそれです。
例
最近では、共通の祖先を見つけるさまざまな方法が登場しています。質問の要件に応じて適切な記述方法を選択してください。
ポータルの例
質問の意味
一つあげてください \(n\) ノード、\(n-1\) エッジのあるツリー。データはツリーを形成することが保証されており、ツリーのルート ノードは \(s\)今はあります \(m\) グループ クエリ。クエリの各グループには 2 つの正の整数が含まれます。 \(a,b\)質問を表明する \(a\) ノード合計 \(b\) ノードの最新の共通祖先。
データ範囲
のために \(30\%\) データ、\(N\その10\)、\(M\le 10\)。
のために \(70\%\) データ、\(N\the 10000\)、\(M\the 10000\)。
のために \(100\%\) データ、\(N\the 500000\)、\(M\the 500000\)。
解決策 1: 暴力的な解決策
ツリーでは、各ノードに対応する深さがあります。深さはルート ノードを基準にしています。見つけるには \(x\)、\(y\) lca 深さは次の場合に固有です。 \(x\) そして \(y\) 深さが同じ場合、親ノードへの各ジャンプにより、深さが常に同じであることが保証されます。これは、親ノードが一致すること、つまり最も近い共通の祖先が見つかったことを確認することのみを必要とします。
したがって、保存する際には、各点の深さを保存する必要があり、各ノードの親ノードも保存する必要があります。
ツリー全体を前処理する必要があり、時間がかかる \（の上）\）単一のクエリの複雑さは \（の上）\）アルゴリズムはシンプルで時間がかかり、期待スコアは 70 点です。
コードは次のとおりです
#include
using namespace std;
const int N=5e5+5;
int n,m,s,d[N],f[N];
vectore[N];
inline void dfs(int u,int fa){
d[u]=d[fa]+1;
f[u]=fa;
for(auto v:e[u]){
if (v!=fa){
dfs(v,u);
}
}
}
inline void solve(int x,int y){
if (d[x]>d[y]){
swap(x,y);
}
while(d[x]>n>>m>>s;
for(int i=1;i<=n-1;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(s,0);
while(m--){
int a,b;
cin>>a>>b;
solve(a,b);
}
return 0;
}
Luogu のデータは少し水っぽいですが、O(n^2) の複雑さで取得できます。100ポイント
解決策 2: 2 倍化アルゴリズム
2 倍化アルゴリズムは、ブルート フォース アルゴリズムの改良版です。二次元を導入することで \(f\) 配列を使用してノードホップの数を減らし、単一のクエリの複雑さを軽減します。 \(O(logn)\)倍増の考え方はSTテーブルの考え方と似ています。 STテーブルが分からない方はこちらを参考にしてください。
意味 \(f[u][i]\) 点を表します \(u\) の \(2^i\) 祖先、\(f[u][i]\) dfs を通じて前処理でき、見つけるのは難しくありません。 \(f[u][i]=f[f[u][i-1]】[i-1]\)、\(u\) の \(2^i\) 祖先というのは、 \(u\) の \(2^{i-1}\) 先祖の \(2^{i-1}\) ご先祖様。
前処理の複雑さ \(O(nlogn)\)単一クエリの複雑さ \(O(logn)\)全体の複雑さ \(O(nlogn+mlogn)\) この問題には簡単に合格できます。100 点を獲得できると予想されます
コードは次のとおりです
#include
using namespace std;
const int N=5e5+5;
int n,m,s,d[N],f[N][21];
vectore[N];
inline void dfs(int u,int fa){
d[u]=d[fa]+1;
f[u][0]=fa;
for(int i=1;(1<d[y]){
swap(x,y);
}
for(int i=20;i>=0;i--){
if (d[x]<=d[y]-(1<=0;i--){
if (f[x][i]==f[y][i]){
continue;
}else{
x=f[x][i],y=f[y][i];
}
}
cout<>n>>m>>s;
for(int i=1;i<=n-1;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(s,0);
while(m--){
int a,b;
cin>>a>>b;
solve(a,b);
}
return 0;
}
解決策 3: dfs order + RMQ アルゴリズム
前提知識、STテーブル なぜまたあなたなのですか？間隔最大の問題を解決するために使用されます。
では、lca は RMQ とどのように関係するのでしょうか?
lca はツリー問題であり、ツリー走査はブリッジ、dfs オーダーを使用できるため、ツリー走査は区間シーケンスになります。
詳細な説明は以下
上の写真の木を例に取ってみましょう
シリアルナンバー：01 02 03 04 05 06 07 08 09 10 11 12 13
深さ：01 02 03 02 03 04 03 04 03 02 01 02 01
ノード：01 02 04 02 05 06 05 07 05 02 01 03 01
このテーブルを入手すると、テーブル内で興味深いものを見つけることができます。たとえば、lca(4,6) を検索する場合、ノード 4 からノード 6 までの任意の間隔を検索し、その間隔内で深さが最小のノードを検索するだけで済みます。この点が lca(4,6) です。
シリアルナンバー \(1\sim 13\) は間隔全体であり、見つかった間隔は次のようになります。 \(3\sim 6\)ここで最小の深さは \(2\)対応するノードは \(2\) ノード。それを証明して自分で調べてください
2次元配列を使用する \(st\) 2次元配列を使用しながら、dfsオーダーで間隔の最小値を維持します\(isdt\)保存間隔の最小値に対応するノード、\(dfn\) 配列レコードの DFS 順序、\(iddfn\) ノードを初めて通過するときの dfs 順序を記録します。
知らせ：
1. \(st\)格納されるのは、dfs order の間隔の最大値です。境界と初期化の問題に注意してください。
2. \(dfn\)配列はdfsオーダーと呼ばれていますが、 \(dfn[i]\) タイムスタンプが \（私\） 時のノード番号
3. 原因 \(st\) 保存されるのは dfs 順序の間隔情報のセクションであるため、渡されるパラメータも dfs 順序である必要があります。
4. 各変数が何を表すかを理解してください。そうでない場合は、私のように調整することになります。 \(2\) 時間
時間計算量は \(O(nlogn+m)\)ただし、スペースのオーバーヘッドが大きく、前処理定数が大きく、期待されるスコアは 100 点です
#include
using namespace std;
const int N=5e5+5;
int n,m,s;
int st[N*2][21],idst[N*2][21],lg[N*2];
int dfn[N*2],d[N*2],times,iddfn[N];
vectore[N];
inline void dfs(int u,int fa){
dfn[++times]=u;
if (iddfn[u]==0)iddfn[u]=times;
d[u]=d[fa]+1;
for(auto v:e[u]){
if (v==fa)continue;
dfs(v,u);
dfn[++times]=u;
}
}
inline void init(){
lg[2]=1;
for(int i=3;i<=2*n;i++){
lg[i]=lg[i/2]+1;
}
for(int i=1;i<=times;i++){
st[i][0]=d[dfn[i]];
idst[i][0]=dfn[i];
}
for(int j=1;j<=20;j++){
for(int i=1;i+(1<r)swap(l,r);
int p=lg[r-l+1];
if (st[l][p]>n>>m>>s;
for(int i=1;i>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(s,0);
init();
while(m--){
int l,r;
cin>>l>>r;
solve(iddfn[l],iddfn[r]);
}
return 0;
}
解決策 4: tarjan アルゴリズム
上記のアルゴリズムはすべてオンライン アルゴリズムですが、lca に対する tarjan のソリューションはオフライン アルゴリズムです。
上記のアルゴリズムと比較して、tarjan アルゴリズムはより安定しており、時間計算量も比較的小さいです。事前知識が必要であり、セットを検索します。
基本的な考え方：
- データの読み取りプロセス中に、クエリの各セットがマップのように保存され、順方向と逆方向が 2 回構築されます。
- ルートノードから開始するトラバース
- ノードをトラバースする \(u\) のすべての子ノード \(v\)これらのポイントを訪問済みとしてマークします
- のように \(v\) 子ノードが存在する場合は 3. を返し、存在しない場合は次のステップに進みます。
- マージ \(v\) 到着 \(u\) 上記の順序を逆にすることはできないことに注意してください。 \(u\) はい \(v\) の親ノード
- すべてを検索 \(u\) クエリが必要な接続されたノード \(v’\)。
- のように \(v’\) 訪問済みですので、ご安心ください \(u\) そして \(v\) 最も最近の共通祖先は、 \(find(v’)\)。
時間の複雑さ \(O(n+m)\)予想スコアは100点です
コードは次のとおりです
#include
using namespace std;
//#define int long long
const int N=5e5+5;
int n,m,s;
int ans[N];
int fa[N];
bitsetvis;
vectore[N];
vector>q[N];
inline int find(int x){
return x==fa[x] ? x : fa[x]=find(fa[x]);
}
inline void tarjan(int u,int father){
vis[u]=true;
for(auto v:e[u]){
if (v==father or vis[v])continue;
tarjan(v,u);
fa[v]=u;
}
for(auto i:q[u]){
int v=i.first,id=i.second;
if (vis[v]){
anshttps://www.cnblogs.com/Emoji-happy/p/23370630=find(v);
}
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n>>m>>s;
for(int i=1;i<=n-1;i++){
int u,v;
cin>>u>>v;
e[u].push_back(v);
e[v].push_back(u);
}
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
if (x==y){
ans[i]=x;
continue;
}
q[x].push_back({y,i});
q[y].push_back({x,i});
}
tarjan(s,0);
for(int i=1;i<=m;i++){
cout< 
