[白俊]3176道路網

[正解ではなく解答記録]
どうろネットワーク
N都市、N-1幹線があり、2つの都市の時間経路が唯一つながっている.2つの都市が複数の都市に入ると,2つの都市を結ぶ道路の中で最も長く最も短い道路を求める.

に近づく

道路はもちろん双方向です.

は、a、bの2つの都市間の経路しか考慮できない.

dfsを使用すると検索時間が長すぎます.

インプリメンテーション

LCA

この問題では,2つの都市間の経路を必要とせず,2つの都市間の経路の中で最も長く最も短い道路が何であるかを見つけ出すだけでよい.
ツリー構造の道路ネットワークでは、a−>bの経路は、a−>aおよびbの最小の共通祖先−>bである.
したがって、aと(aと(bの最小共通祖先)との間の最長、最短経路を求め、bと(aとbの最小共通祖先)との間の最長、最短を求め、2つの出力を比較すればよい.
LCA(最小共通祖先)を実施する.
LCAのデフォルト設定は次のとおりです.

任意のノードをキャプチャし、その深さを0、そのサブノードの深さを1、そのサブノードの深さを2...このようにDFSにより深さを求める.

の2つのノード番号を入力した場合、2つのノードの深さを比較し、深さが浅いノードと同じになるまで、より深いノードを親ノードに沿って上に移動します.

の深さが同じである場合、両方のノードは、同じ番号になるまで親に沿って上に進みます.

ノード番号が同じ場合、ノードはLCAです.

でもよく考えてみるとこの問題は10万個ありますn

(1本)1-2-3-4...-9999999-1000というのは直線から入ってくると1万100000というのは?
->同じ深さを2回で調整するには、10万個のノードにアクセスする必要があります.

(5万本)50000から分かれ、左が49999-499998に減って1になり、右が50001-50002に増えて10万になるグラフの中で、1、10万があれば?
->3番でLCAを検索するには、10万個のノードにアクセスする必要があります.

遅い.
親に急速に上昇する方法を見つける必要があり、疎アレイは急速に上昇することができます.

快速LCA

-> 疎配列の説明を含む問題(リンク)
上記の問題ではまばらな配列の説明をしたので省略します.

1.深さを求める

void dfs(int node) {
	check[node] = true;
	for (int i = 0; i < v[node].size(); i++){
		if (!check[v[node][i]]) {
			table[0][v[node][i]] = node
			dfs(v[node][i]);
		}
	}
}
void make_table(){
	for (int i = 1; i <= 17; i++) {
			for (int j = 1; j <= n; j++) {
				table[i][j]= table[i-1][table[i-1][j]]t;
			}
	}
}

疎配列を生成する2つのコード.上表[0]から下表[1~n]へ
table[0]を求める場合、LCAに必要な深さも求めるように変更します.

void dfs(int node) {
	check[node] = true;
	for (int i = 0; i < v[node].size(); i++){
		if (!check[v[node][i]]) {
			table[0][v[node][i]] = node
            depth[v[node][i]] = depth[node] + 1;//깊이 구하기
			dfs(v[node][i]);
		}
	}
}

2.奥行きの調整

2つのノード番号を入力する場合は、奥行きの深いノードを浅い番号に上げる必要があります.
ビットを使用して、何番目の親に移動するかを決定できます.
a=奥行き13=1101
b=奥行き3=001
1101 - 0011 = 13 - 3 = 1010 = 10
aをaの2番目の親の8番目の親とすると、その深さは同じです.

if (depth[a] > depth[b]) {
			int c = depth[a] - depth[b];//차 구하기
			int Count = 0;//2^Count번째 부모를 나타낼 때 사용
			while (c > 0) {
				if ((c & 1) == 1) {//만약 가장 앞 비트가 1이라면
					a = table[Count][a];//2^Count번째 부모로 올라감
				}
				c = c >> 1;//c의 비트를 한칸씩 앞으로 당김
				Count++;//Count 증가
			}
		}

		if (depth[b] > depth[a]) {//이하 같음
			int c = depth[b] - depth[a];
			int Count = 0;
			while (c > 0) {
				if ((c & 1) == 1) {
					b = table[Count][b];
				}
				c = c >> 1;
				Count++;
			}
		}

3.アップロード

2つのノードの深さが同じ場合があります.この場合、3回省略する.
次に、2つのノードが深さ調整を行った後の違いを示します.
任意の2つのノードa,bにおいて、最小の共通祖先の後に上昇し続けても、その祖先は同じである.
だから、単純な祖先は同じで、これは最小の共通の祖先です!いけません.
したがって、2つのノードは、非共通の祖先ノードに昇格し続けます.次にセルを上に移動すると、ノードは最小の共通祖先になるため、最小の共通祖先が検索されます.
共通の祖先ではなく、ノードにアップロードし続けましょう.
まず上のまばらな配列の文章に書いてある
i番ノードから2^(17-1)の2番目の親ノードに移動できない場合、2^(16-1)の2番目の親ノードに移動でき、2^(15-1)、2^(14-1)に移動できます.親と一緒に移動しても2^(17-1)より遠くは行けません.
1000 > 0111
したがって、親ノードのすべてのノードでの移動は、1つのリング17〜0の周りを回るだけでよい.
これもこれに適用されます.
table[17]に移動し、2つのノードの親ノードが異なる場合、同じノードを上に移動します.

if (a != b) {
		for (int i = 17; i >= 0; i--) {
			if (table[i][a].first != table[i][b].first) {
				a = table[i][a];
				b = table[i][b];
			}
		}
		a = table[0][a];
		b = table[0][b];
}

for文が終了すると、aおよびbは少なくとも共通の祖先の子に位置する.
したがって、table[0]を介してセルが1つ上昇すると、aおよびbは最小の共通祖先を指す.

4.LCA出力

2、3から4の場合、aおよびbは同じノードを指す.
LCAなので、出力すればいいです.

printf("%d",a);

もしあなたがそれができるなら.
別の質問(リンク)を解くことができます.
この問題では,道路の最大と最小の長さを求めなければならない.

最大最小値を求める

テーブルとベクトルの定義は、幹線に重みがあり、テーブルに最大値と最小値を格納する必要があるため、少し変更します.

vector<pair<int,long long>> v[100002] //노드번호와 가중치
pair<int,pair<long long,long long>>table[18][100002];//2^n번 부모의 번호,2^n번 부모까지의 최대, 최소

DFSとテーブルの作成セクションで、最大ストレージ容量と最小ストレージ容量に変更します.
DFSでは、最初の親の最大値と最小値が同じです.
テーブルの作成セクションには、i番ノードから4番目の親ノードまでの最大最小=(i番ノードから2番目の親ノードまでの最大最小、i番ノードの2番目の親ノードから2番目の親ノードまでの最大最小)の最大および最小が含まれます.

void dfs(int node) {
	check[node] = true;
	for (int i = 0; i < v[node].size(); i++) {
		if (check[v[node][i].first] == false) {
			depth[v[node][i].first] = Rank[node]+1;
			table[0][v[node][i].first] = {node,{v[node][i].second,v[node][i].second}};//최대 최소 저장
			dfs(v[node][i].first);
		}
	}
}

void make_table() {
	for (int i = 1; i <= 16; i++) {
		for (int j = 1; j <= n; j++) {
			table[i][j] = {table[i-1][table[i-1][j].first].first,//노드 번호
				{ 
				  max(table[i-1][j].second.first,table[i-1][table[i-1][j].first].second.first),//최대
				  min(table[i - 1][j].second.second,table[i - 1][table[i - 1][j].first].second.second)//최소
				}
			};
		}
	}
}

3番と4番から親ノードにアップグレードするときに、コードを追加して、現在の最大値、アップグレード中の最大値、最小値の最大値を格納します.

ll MaxA = 0;
ll MinA = MAX;
ll MaxB = 0;
ll MinB = MAX;
//-----------------------------------------------
if (depth[a] > depth[b]) {
		int c = depth[a] - depth[b];
		int Count = 0;
		while (c > 0) {
			if ((c & 1) == 1) {
				MaxA = max(MaxA,table[Count][a].second.first);
				MinA = min(MinA,table[Count][a].second.second);
				a = table[Count][a].first;
			}
			c = c >> 1;
			Count++;
		}
}

//--------------------------------------------

if (a != b) {
		for (int i = 17; i >= 0; i--) {
			if (table[i][a].first != table[i][b].first) {
				MaxA = max(MaxA, table[i][a].second.first);
				MinA = min(MinA, table[i][a].second.second);
				MaxB = max(MaxB, table[i][b].second.first);
				MinB = min(MinB, table[i][b].second.second);
				a = table[i][a].first;
				b = table[i][b].first;
			}
		}

		MaxA = max(MaxA, table[0][a].second.first);
		MinA = min(MinA, table[0][a].second.second);
		MaxB = max(MaxB, table[0][b].second.first);
		MinB = min(MinB, table[0][b].second.second);
		a = table[0][a].first;
		b = table[0][b].first;
}

私はaとbを最小の2つに分けましたが、1つでもいいです.

答えの出力

上記の処理が完了した後、aとbを分離すると、最大はMaxA、MaxB、最小はMina、Minbに格納される.
分割がない場合、最大最小値はMaxに格納されます.
前者の場合、出力は次のようになります.

printf("%lld %lld\n",min(MinA,MinB),max(MaxA,MaxB));

後者の場合は、次のように出力できます.

printf("%lld %lld\n",Min,Max);

の最後の部分

O(nlogn)LCAを知っていれば、これは解決しやすい問題のようです.
構造体でtableを宣言すれば、もっときれいになるはずです.
終わりだ!