Shiraz University Local Contest 2011 C, UVa-12379 : Central Post Office

問題概要

ノード数V(<10^4)の木が与えられる。ある始点から出発して全ての頂点に到達するまでの総経路長の最小値を求める問題。

考えたこと

• どこかで、というかCodeForcesで似た問題を解いた記憶がある。
• 普通のEuler tourだと2*V-2が総経路長になるが、戻ってくる必要がないのでdist(start, goal)の分だけ差っ引くことができる。
• なのでstart, goalを最大化してやればよい。すなわち木の直径。
• 後は書くだけ。stack overflowしないことを確認してDFSで書いた。

本番で通ったコード

計算量O(V)。

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 1e4;

int N;
vector<int> graph[MAX_N];
bool visited[MAX_N];
int dist[MAX_N];

void init(){
	scanf("%d", &N);

	for(int i=0; i<N; i++){
		graph[i].clear();
	}

	for(int i=0; i<N; i++){
		int K;
		scanf("%d", &K);
		for(int j=0; j<K; j++){
			int x;
			scanf("%d", &x);
			x--;
			graph[i].push_back(x);
		}
	}
}

void dfs(int v){
	visited[v] = true;
	for(int i=0; i<(int)graph[v].size(); i++){
		int u = graph[v][i];
		if(!visited[u]){
			dist[u] = dist[v] + 1;
			dfs(u);
		}
	}
}

int sub(){
	memset(visited, false, sizeof(visited));
	dist[0] = 0;
	dfs(0);
	int p = max_element(dist, dist+N) - dist;
	memset(visited, false, sizeof(visited));
	dist[p] = 0;
	dfs(p);

	return *max_element(dist, dist+N);
}

int solve(){
	return 2*N-2 - sub();
}

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		init();
		printf("%d\n", solve());
	}

	return 0;
}