Submission #230699

---

Source Code Expand

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace AtCoderBeginner014
{
	class Program
	{
		public static bool[] check;

		static void Main(string[] args)
		{
			int N = int.Parse(Console.ReadLine());
			int[] x = new int[ N ];
			int[] y = new int[ N ];
			for (int i = 0; i < N - 1; ++i) {
				string[] input = Console.ReadLine().Split();
				x[ i ] = int.Parse(input[ 0 ]) - 1;
				y[ i ] = int.Parse(input[ 1 ]) - 1;
			}
			int Q = int.Parse(Console.ReadLine());
			int[] a = new int[ Q ];
			int[] b = new int[ Q ];
			for (int i = 0; i < Q; ++i) {
				string[] input = Console.ReadLine().Split();
				a[ i ] = int.Parse(input[ 0 ]) - 1;
				b[ i ] = int.Parse(input[ 1 ]) - 1;
			}

			for (int i = 0; i < Q; ++i) {
				x[ N - 1 ] = a[ i ];
				y[ N - 1 ] = b[ i ];

				check = new bool[ N ];
				Stack<int> stack = new Stack<int>();
				stack.Push(x[ N - 1 ]);
				int result = recurse(N, x, y, 0, -1, x[ N - 1 ]);
				Console.WriteLine(result);
			}

			Console.ReadLine();
		}

		public static int recurse(int N, int[] x, int[] y, int sum, int from, int now) {

			Stack<int> stack = new Stack<int>();

			// vを訪れる
			int v = now;
			check[ v ] = true;
			++sum;

			// vから繋がる頂点を追加
			for (int i = 0; i < N; ++i) {
				for (int j = 0; j < 2; ++j) {
					int origin = -1;
					int target = -1;
					if (j == 0) {
						origin = x[ i ];
						target = y[ i ];
					} else {
						origin = y[ i ];
						target = x[ i ];
					}
					if (origin == v) { // vから繋がる頂点を発見
						if (target == x[ N - 1 ] && target != from) { // 最初に帰った
							return sum;
						}
						if (!check[ target ]) {
							stack.Push(target);
						}
					}
				}
			}

			while (stack.Count > 0) {
				int to = stack.Pop();
				int ret = recurse(N, x, y, sum, v, to);
				if (ret > 0) { // スタート地点に到達した
					return ret;
				}
			}

			return 0;
		}
	}
}

Submission Info

Judge Result