Codeforces #29 (div2) D "AntOnTheTree"

問題：http://codeforces.com/contest/29/problem/D

※なんか記事が消えてたので再投下．

本番．

めんどくさかったのでワーシャルフロイドで経路求めて，
ルート/リーフ移動時に通った道を埋めながら復元．

import java.util.*;

public class D_AntOnTheTree {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt() + 1;
		long[][] a = new long[n][n];
		int[][] p = new int[n][n];
		for (int i = 1; i < n; ++i) {
			Arrays.fill(a[i], Integer.MAX_VALUE);
			a[i][i] = 0;
		}
		for (int i = 0; i < n - 2; ++i) {
			int x = s.nextInt(), y = s.nextInt();
			a[x][y] = a[y][x] = 1;
			p[x][y] = x;
			p[y][x] = y;
		}
		for (int t = 1; t < n; ++t) {
			for (int i = 1; i < n; ++i) {
				for (int j = 1 + i; j < n; ++j) {
					long l = a[i][t] + a[t][j];
					if (a[i][j] > l) {
						a[i][j] = a[j][i] = l;
						p[i][j] = p[t][j];
						p[j][i] = p[t][i];
					}
				}
			}
		}
		List<Integer> leavs = new ArrayList<Integer>();
		for (; s.hasNext();) {
			leavs.add(s.nextInt());
		}
		leavs.add(1);
		List<Integer> path = new ArrayList<Integer>();
		path.add(1);
		int e = 1;
		for (int lf : leavs) {
			List<Integer> path2 = path(e, lf, p);
			if (path2 == null) {
				System.out.println(-1);
				return;
			}
			path.addAll(path2);
			path.remove(path.size() - 1);
			e = lf;
		}
		System.out.println(path.toString().replaceAll("[\\[\\],]", ""));
	}

	static List<Integer> path(int from, int to, int[][] p) {
		List<Integer> path = new ArrayList<Integer>();
		path.add(to);
		while (from != to) {
			int tmp = p[from][to];
			if (p[tmp][to] < 1) {
				return null;
			}
			path.add(to);
			p[tmp][to] = 0;
			to = tmp;
		}
		Collections.reverse(path);
		return path;
	}
}