Atcoder解いてみた AtCoder Beginner Contest E - Tree and Hamilton Path 2

AtCoder Beginner Contest E - Tree and Hamilton Path 2

問題はこちら

回答

全ての点を通り、ある点にたどり着いた時の距離は、以下の図の黒線で示した経路の距離から赤線の距離を引けばいい
黒線の距離は、全ての辺の長さの和を2倍したものである
今回は、赤線の距離を最大化すればいい
そのためには、グラフの直径を求めればいい
グラフの直径を求めるには、適当な点からDFSし、最も遠い点を求め(点1)、その点からもう一度DFSし最も遠い点(点2)を求め、点1-2間の距離を求めればいい

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>

struct Edge {
	long long t;
	long long c;
};

struct DfsRes {
	long long p;
	long long c;
};

int N;
std::vector<std::vector<Edge>> G;

std::vector<bool> seen;


DfsRes dfs(const int& s, DfsRes dfsResP) {
	seen[s] = true;

	DfsRes tmpDfsRes = dfsResP;
	// sの隣接点を見る
	for (const Edge& e : G[s]) {
		// 隣接点が未訪問
		if (seen[e.t] == false) {
			// 隣接点にいざ訪問するときに、最長距離と最長距離をとるときの点を更新
			// DFSに区切りがつき、戻ってくることを考慮し、更新
			// 各隣接点を訪問しきった後のdfsResの中で最もいい結果を採用
			DfsRes dfsRes = dfs(e.t, { e.t, dfsResP.c + e.c });
			// dfsの再起関数を抜けると、DFSに区切りがつき、戻ってくる
			if (dfsRes.c > tmpDfsRes.c) {
				tmpDfsRes = dfsRes;
			}
		}
	}

	return tmpDfsRes;
}

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N;

	G.resize(N);

	long long sumCost2 = 0;
	for (int i = 1; i < N; i++) {
		int a, b;
		long long c;

		std::cin >> a >> b >> c;

		a--;
		b--;

		// 無向グラフ
		Edge e = { b,c };
		G[a].push_back(e);

		e = { a,c };
		G[b].push_back(e);

		sumCost2 += 2 * c;
	}

	// dfsを2回
	// 適当な点から最も遠い点を見つけ、その点から最も遠い点を見つける

	// 初期化・1回目
	int s = 0;
	DfsRes dfsRes = { s,0 };
	seen.resize(N);
	dfsRes = dfs(s, dfsRes);

	// 初期化・2回目
	s = dfsRes.p;
	dfsRes = { s,0 };
	std::fill(seen.begin(), seen.end(), false);
	dfsRes = dfs(s, dfsRes);
	
	long long ans = sumCost2 - dfsRes.c;
	std::cout << ans << std::endl;

	return 0;
}