水平1167、ツリーの直径ツリー、DFS

https://www.acmicpc.net/problem/1167

1.アイデア

重み付けシェイプ(ツリー)の頂点間の距離(幹線重み付け)フィーチャー

最も遠い2つの頂点がv1である場合、v2である.
他の任意の頂点v_anyから最も遠い頂点はv1またはv2である.

1)任意の1つの頂点と1つの最も遠い頂点を求めます(求めた最も遠い頂点:v1)

任意の頂点v_anyからDFSの実行を開始

2)最も遠い頂点v1(v1)と最も遠い頂点を求めます:v2)

頂点v1からDFSの実行を開始
=>v1とv2は、ツリーに最も近い2つの頂点です.
=>DFSは2つの最も遠い頂点v1、v2(木の直径)

を求めます
ノートを間違える:タイムアウト

全頂点1 ~ vの各頂点に対してDFSナビゲーション

を実行

DFSが最後のv頂点に到達したときの最大直径値のリフレッシュ

全時間複雑度=最大10^5頂点
=>2 x 10^5 x 10^5=2 x 10^10>>2億(2秒)

2.資料構造

List<Pair>[],ArrayList<Pair>[]:隣接リスト
ex)lists[1]:1番頂点との接続情報を保存Pair(頂点番号、幹線距離)

boolean[]:アクセス確認

3.時間複雑度

DFS 1実行:O(V+E)=2 x 10^5

V:最大10^5,E:約10^5

全時間複雑度=DFS 2回
=>2 x(2 x 10^5)=4 x 10^5<2億(2秒)

コード#コード#

import java.io.*;
import java.util.*;

class Pair {
	public int vertex;	// 연결된 정점 번호
	public int distance;	// 간선 거리

	public Pair(int vertex, int distance) {
		this.vertex = vertex;
		this.distance = distance;
	}
}

public class Main {
	static int v;			// 트리 정점(노드) 개수, 정점 번호: 1 ~ v
	static int maxR = Integer.MIN_VALUE;
	// 출력 값: 트리의 최대 지름 (두 정점 사이의 거리 중, 가장 긴 것)
	static List<Pair>[] lists;	// 인접 리스트
	static boolean[] check;
	static int vertex;		// 임의의 정점과 가장 먼 정점 (가장 먼 두 정점 v1, v2 둘 중에 하나)

	/* vertexIdx: 현재 정점 번호, totalDistance: 누적 거리 */
	static void dfs(int vertexIdx, int totalDistance) {
		check[vertexIdx] = true;

		List<Pair> list = lists[vertexIdx];
		for (Pair p : list) {
			if (!check[p.vertex])
				dfs(p.vertex, totalDistance + p.distance);
		}

		if (maxR < totalDistance) {
			maxR = totalDistance;
			vertex = vertexIdx;	// 첫 번째 DFS 로 가장 먼 두 정점 중, v1 구함
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(
				new InputStreamReader(System.in)
		);
		StringTokenizer st;

		v = Integer.parseInt(br.readLine());
		lists = new ArrayList[v + 1];		// [1 ~ v] 사용
		for (int i = 1; i <= v; i++)
			lists[i] = new ArrayList<>();

		for (int i = 1; i <= v; i++) {
			st = new StringTokenizer(br.readLine());

			int startNode = Integer.parseInt(st.nextToken());
			while (st.hasMoreTokens()) {
				int destNode = Integer.parseInt(st.nextToken());
				if (destNode == -1)
					break;
				int distance = Integer.parseInt(st.nextToken());

				lists[startNode].add(new Pair(destNode, distance));
				lists[destNode].add(new Pair(startNode, distance));
			}
		}

		// 임의의 정점에서 가장 먼 정점 v1 구하기 (vertex 에 저장)
		check = new boolean[v + 1];
		dfs(1, 0);

		// 정점 v1 과 가장 먼 정점 v2 구하기 => v1 과 v2 는 트리에서 가장 먼 두 정점
		// 트리의 최대 지름 계산
		check = new boolean[v + 1];
		dfs(vertex, 0);

		System.out.println(maxR);
	}
}