読者です 読者をやめる 読者になる 読者になる

tookunn’s diary

主に競技プログラミング関係

RUCP2016 Day3 C 成長する点 - Growing Point -

問題

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=C

割と問題文通りにやるだけなのだけど、幾何っぽいというのもあって方針は合ってるが実装のバグが取れないのが辛かった

考察

一番最初に拠点0と最も近い餌との間に直線を追加、そこから下記の手順をM-1回繰り返していく

  1. 追加した直線と粘菌網に含まれていない餌の中で一番近い餌を選ぶ(この餌をX)
  2. その餌Xと粘菌網に含まれている中で一番近い餌を選ぶ(この餌をY)
  3. 餌Xと餌Yとの間に直線を追加し、その直線の長さを解に加える。1に戻る。

公式解説:
http://www.slideshare.net/hcpc_hokudai/2016day3c

ソースコード

import java.awt.geom.Line2D;
import java.awt.geom.Point2D;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main implements Runnable{
	int N,M,X,Y;
	int[] px,py;
	double[] min;
	boolean[] used;
	public void solve() {
		N = nextInt();
		M = nextInt();
		X = nextInt();
		Y = nextInt();
		px = new int[N+1];
		py = new int[N+1];
		px[0] = X;
		py[0] = Y;
		for(int i = 1;i <= N;i++){
			px[i] = nextInt();
			py[i] = nextInt();
		}

		double ans = 0.0;
		used = new boolean[N+1];
		min = new double[N+1];

		int minInd1 = 1;
		for(int i = 1;i <= N;i++){
			double dis = Point2D.distance(px[0], py[0], px[i], py[i]);
			min[i] = dis;
			if(dis < min[minInd1]){
				minInd1 = i;
			}
		}

		Line2D.Double line = new Line2D.Double(px[0],py[0],px[minInd1],py[minInd1]);
		used[minInd1] = true;
		used[0] = true;
		ans += min[minInd1];

		for(int i = 0;i < M-1;i++){

			for(int j = 0;j <= N;j++){
				if(used[j])continue;
				min[j] = Math.min(min[j],line.ptSegDist(px[j], py[j]));
			}

			int minInd2 = -1;
			for(int j = 0;j <= N;j++){
				if(used[j])continue;
				if(minInd2 == -1)minInd2 = j;
				else if(min[j] < min[minInd2]){
					minInd2 = j;
				}
			}

			double minDis3 = Double.MAX_VALUE;
			int minInd3 = -1;
			for(int j = 0;j <= N;j++){
				if(used[j]){
					double dis = Point2D.distance(px[minInd2], py[minInd2], px[j], py[j]);
					if(dis  < minDis3){
						minDis3 = dis;
						minInd3 = j;
					}
				}
			}
			ans += minDis3;
			used[minInd2] = true;
			line.setLine(px[minInd2], py[minInd2], px[minInd3], py[minInd3]);
		}

		out.println(ans);
	}

	public static void main(String[] args) {
		new Thread(null,new Main(),"",32 * 1024 * 1024).start();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

	@Override
	public void run() {
		out.flush();
		new Main().solve();
		out.close();

	}
}

RUCP2016 Day3 B 周期数列 - Periodic Sequence -

考察

考えられる周期tをそれぞれ試していくだけ

N = ktから,tはNを割り切る数なのでそこまで多くない

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.NoSuchElementException;

public class Main implements Runnable{
	int N;
	int[] S;
	public void solve() {
		N = nextInt();
		S = new int[N];
		for(int i = 0;i < N;i++){
			S[i] = nextInt();
		}

		ArrayList<Integer> ts = new ArrayList<Integer>();
		for(int i = 1;i <= N;i++){
			if(N%i==0){
				ts.add(i);
			}
		}
		int ans = 0;
		for(int t : ts){

			int k = N / t;
			boolean flag = false;
			for(int i = 0;i < t;i++){
				for(int j = 0;j < k;j++){
					if(S[j * t + i]==S[i])continue;
					flag = true;
					break;
				}
				if(flag)break;
			}

			if(!flag){
				ans = Math.max(ans, k);
			}
		}

		out.println(ans);
	}

	public static void main(String[] args) {
		new Thread(null,new Main(),"",32 * 1024 * 1024).start();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

	@Override
	public void run() {
		out.flush();
		new Main().solve();
		out.close();

	}
}

Codeforces #389 Div2 A~C


考察

rとdを導出する式を見つけ出すのに結構時間掛かってしまった

r = ceil(K/(2M))
d = ceil( (K-2M(r-1))/2)
RかLかは偶奇を見ればよい

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class A {
	int N,M,K;
	public void solve() {
		N = nextInt();
		M = nextInt();
		K = nextInt();


		int r = (int)Math.ceil(((double)K/(2*M)));
		int d = (int)Math.ceil((K-((double)r-1)*2*M)/2);
		char s = K%2==1 ? 'L' : 'R';
		out.println(r + " " + d + " " + s);
	}

	public static void main(String[] args) {
		out.flush();
		new A().solve();
		out.close();
	}


	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

考察

文字列s,tを同時に一文字ずつ見ていき,その文字の対応を保持していく。

alpha[a] == b && alpha[b] == aの場合は既にaとbの対応が出来ているのでスルー

alpha[a] == -1 && alpha[b] == -1の場合はまだa,b両方に何も対応が出来ていないので,aとbを対応付ける

それ以外の場合は-1

その後はalphaを順に見ていき対応する文字を出力していく。

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class B {
	String s,t;
	int[] alpha;
	public void solve() {
		s = next();
		t = next();
		alpha = new int[26];
		Arrays.fill(alpha,-1);
		for(int i = 0;i < s.length();i++){

			int a = s.charAt(i) - 'a';
			int b = t.charAt(i) - 'a';
			if(alpha[a] == b && alpha[b] == a){
				continue;
			}else if(alpha[a] == -1 && alpha[b] == -1){
				alpha[b] = a;
				alpha[a] = b;
			}else{
				out.println(-1);
				return;
			}
		}
		ArrayList<int[]> ans = new ArrayList<int[]>();
		for(int i = 0;i < 26;i++){
			if(i == alpha[i])continue;
			if(alpha[i] == -1)continue;
			if(i == alpha[alpha[i]]){
				ans.add(new int[]{i,alpha[i]});
				alpha[alpha[i]] = -1;
				alpha[i] = -1;
			}
		}

		out.println(ans.size());
		for(int[] i : ans){
			char a = (char)(i[0]+'a');
			char b = (char)(i[1]+'a');
			out.println(a + " " + b);
		}
	}

	public static void main(String[] args) {
		out.flush();
		new B().solve();
		out.close();
	}
}

考察

これはEditorial見たけどいまいちよく分からない。
codeforces.com

とりあえず,進んだ方向と逆方向に進むことがわかったら,その度にカウントするみたいな感じっぽい。

与えられた文字列Sを先頭から1文字ずつ見ていき,文字の対応を保持する。

見ている文字S[i]の対となる文字がiより前に出現していたらその文字同士を対応付けて,その他の保持している対応をリセットする。

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.NoSuchElementException;

public class C {
	int N;
	char[] ch;
	boolean[] used;
	public void solve() {
		N = nextInt();
		ch = next().toCharArray();
		used = new boolean[4];
		int ans = 1;
		for(int i = 0;i < N;i++){
			if(ch[i]=='L'){
				if(used[1]){
					ans++;
					Arrays.fill(used,false);
				}
				used[0] = true;
			}else if(ch[i]=='R'){
				if(used[0]){
					ans++;
					Arrays.fill(used,false);
				}
				used[1] = true;
			}else if(ch[i]=='U'){
				if(used[3]){
					ans++;
					Arrays.fill(used,false);
				}
				used[2] = true;
			}else if(ch[i]=='D'){
				if(used[2]){
					ans++;
					Arrays.fill(used,false);
				}
				used[3] = true;
			}
		}
		out.println(ans);
	}

	public static void main(String[] args) {
		out.flush();
		new C().solve();
		out.close();
	}
}

Codeforces #388 Div2 A~C

A問題

codeforces.com

考察

Nは2または3だけで表すことが出来るので,2で出来るだけ表すようにして,Nが2で割り切れなかったら最後の2を3にすればよい。

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class A {
	int N;
	public void solve() {
		N = nextInt();
		out.println(N/2);
		for(int i = 0;i < N/2 - N%2;i++){
			if(i != 0)out.print(" ");
			out.print(2);
		}

		if(N%2==1)out.print(" 3");
		out.println();

	}

	public static void main(String[] args) {
		out.flush();
		new A().solve();
		out.close();
	}


	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}

B問題

codeforces.com

考察

与えられた3点を使って平行四辺形を作ることができる残り1点の候補は3つだけ

与えられた3点をA,B,Cとし,求める残り1点をDとするとベクトルAB,ACと点Aの和を求めるとDの座標が分かる。

参考にさせて頂いた解説記事:
pekempey.hatenablog.com

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.NoSuchElementException;

public class B {
	private class V{
		int x,y;
		public V(int x,int y){
			this.x = x;
			this.y = y;
		}
	}
	public void solve() {
		V[] v = new V[3];
		for(int i = 0;i < 3;i++){
			v[i] = new V(nextInt(),nextInt());
		}

		HashSet<int[]> set = new HashSet<int[]>();

		for(int i = 0;i < 3;i++){
			int j = i + 1;
			int k = j + 1;
			j %= 3;
			k %= 3;

			int x = v[i].x + v[j].x - v[i].x + v[k].x - v[i].x;
			int y = v[i].y + v[j].y - v[i].y + v[k].y - v[i].y;

			set.add(new int[]{x,y});
		}
		out.println(set.size());
		for(int[] a : set){
			out.println(a[0] + " " + a[1]);
		}
	}

	public static void main(String[] args) {
		out.flush();
		new B().solve();
		out.close();
	}
}

C問題

codeforces.com

考察

問題文通りにシュミレーションした

与えられた文字列Sを先頭から見ていき,もしその文字が投票権を持っていたら,今見ている文字と対となる文字の中で次に呼ばれる可能性がある文字の投票権を打ち消す。

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;
import java.util.TreeSet;

public class C {
	int N;
	String s;
	public void solve() {
		N = nextInt();
		s = next();

		TreeSet<Integer> D = new TreeSet<Integer>();
		TreeSet<Integer> R = new TreeSet<Integer>();
		for(int i = 0;i < N;i++){
			if(s.charAt(i) == 'D'){
				D.add(i);
			}else{
				R.add(i);
			}
		}
		for(int i = 0;R.size() > 0 &&  D.size() > 0;i++,i%=N){
			if(s.charAt(i) == 'D'){
				if(!D.contains(i))continue;
				if(R.higher(i) != null){
					R.remove(R.higher(i));
				}else{
					R.remove(R.lower(i));
				}
			}else{
				if(!R.contains(i))continue;
				if(D.higher(i) != null){
					D.remove(D.higher(i));
				}else{
					D.remove(D.lower(i));
				}
			}
		}

		if(D.size() > 0){
			out.println("D");
		}else{
			out.println("R");
		}
	}

	public static void main(String[] args) {
		out.flush();
		new C().solve();
		out.close();
	}
}

RUPC2016 Day3 A マイナンバー - My Number -

問題

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day3&pid=A

これは当時本番で解いたのでそこまで苦労しないで解けた感(実装は時間掛かった)

考察

?のところに0~9までの数字を当てはめて実際にそのマイナンバーでチェックディジットが一致するかどうかを見ていけば良い。

複数の数字でチェックディジットが一致した場合はMUTLIPLEを出力
1つだけの数字でチェックディジットが一致した場合はその数字を出力

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.NoSuchElementException;

public class Main implements Runnable{
	String s;
	public void solve() {
		s = next();
		ArrayList<Integer> list = new ArrayList<Integer>();

		for(int i = 0;i < 10;i++){
			char[] ch = s.toCharArray();
			for(int j = 0;j < 12;j++)
				if(ch[j] == '?')
					ch[j] = (char)(i + '0');
			int digit = 0;
			for(int j = 11;j >= 1;j--){
				int Q = j >= 7 ? j - 5 : j + 1;
				digit += (ch[(11-j)]-'0') * Q;
			}
			digit %= 11;
			if(digit <= 1)digit = 0;
			else digit = 11 - digit;

			if(digit+'0' == ch[11])list.add(i);
		}

		if(list.size() > 1)out.println("MULTIPLE");
		else out.println(list.get(0));
	}

	public static void main(String[] args) {
		new Thread(null,new Main(),"",32 * 1024 * 1024).start();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

	@Override
	public void run() {
		out.flush();
		new Main().solve();
		out.close();

	}
}

RUPC2016 Day2 G Max Pig Noodle

問題

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=G

誤読というか,交換人と交換しなくていいパターンあるの読み取れなくて苦戦したが,自力で解けたので良かった。

考察

当初,N人の交換人との交換をどの順番に行っていくかを考えていたけど,順番を決めていくと計算量がどう考えても間に合わなそうだったので考え直した。

そこで,順番を考えずにi番目の交換人と「交換する(方法1,方法2)」「しない」をやっていき,N番目の交換人との操作まで終わって最終的に「うまか棒の数」と「ふがしの数」が0未満の数になっていなければその状態はあり得ると考えられるので,その状態での「ブタメソの数」と今までの「ブタメソの数」の最大値とのmaxを取る。
これをそれぞれの状態をメモ化しながら全パターン試していく。

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.NoSuchElementException;

public class Main implements Runnable{
	int N,X,Y;
	int[] a,b,c,d;
	int[][][] dp;

	public int dfs(int n,int x,int y){

		if(n >= N){
			if(x < 300 || y < 300)return -1;
			return 0;
		}

		if(dp[n][x][y] != Integer.MIN_VALUE){
			return dp[n][x][y];
		}

		int ret = -1;

		{
			int tmp = dfs(n + 1,x - a[n],y + b[n]);
			if(tmp != -1){
				ret = Math.max(ret,tmp);
			}
		}

		{
			int tmp = dfs(n + 1,x,y - c[n]);

			if(tmp != -1){
				ret = Math.max(ret,tmp + d[n]);
			}
		}

		{
			int tmp = dfs(n + 1,x,y);

			if(tmp != -1){
				ret = Math.max(ret,tmp);
			}
		}
		return dp[n][x][y] = ret;
	}

	public void solve() {
		N = nextInt();
		X = nextInt();
		Y = nextInt();


		a = new int[N];
		b = new int[N];
		c = new int[N];
		d = new int[N];
		for(int i = 0;i < N;i++){
			a[i] = nextInt();
			b[i] = nextInt();
			c[i] = nextInt();
			d[i] = nextInt();
		}

		dp = new int[N][901][901];
		for(int i = 0;i < N;i++){
			for(int j = 0;j < 901;j++){
				for(int k = 0;k < 901;k++){
					dp[i][j][k] = Integer.MIN_VALUE;
				}
			}
		}
		int ans = dfs(0,X + 300,Y + 300);
		out.println(ans == -1 ? 0 : ans);
	}

	public static void main(String[] args) {
		new Thread(null,new Main(),"",32 * 1024 * 1024).start();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}

	@Override
	public void run() {
		out.flush();
		new Main().solve();
		out.close();

	}
}

RUPC2016 Day2 D Courage Test

考察

まず,頂点uと頂点vから同じ回数しか移動できないので,Nが奇数の場合はNoになる。

次は,頂点uと頂点vそれぞれから各頂点の最短距離を記憶しておく。ダイクストラで求めても良いが,辺のコストは1なので普通にQueueを使った方が早い。

ここで,頂点u と頂点vそれぞれから最短距離がN/2の頂点を覚えておく。(実は最短距離がN/2になる頂点数は少ない)
頂点uまたは頂点vどちらかの頂点から最短距離がN/2の頂点が存在しない場合はNoとなる。
そして,(頂点uから最短距離がN/2の頂点)×(頂点vから最短距離がN/2の頂点)の組み合わせを全部試して,それぞれの最短距離の経路が被らないものがあればYesとなる。

ソースコード

import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.NoSuchElementException;

public class Main{
	static final int INF = (int)1e9 + 7;
	int N,u,v;
	ArrayList<Integer>[] G;
	int[] prev1,prev2;

	public void dijkstra(int s,int[] dis,int[] prev){
		Arrays.fill(prev, -1);
		Arrays.fill(dis, INF);
		dis[s] = 1;

		ArrayDeque<int[]> q = new ArrayDeque<int[]>();
		q.add(new int[]{s,1});

		while(q.size() > 0){
			int[] p = q.poll();
			if(dis[p[0]] < p[1])continue;
			for(int n : G[p[0]]){
				if(dis[p[0]]+1 <= N/2 && dis[n] > dis[p[0]]+1){
					dis[n] = dis[p[0]]+1;
					q.add(new int[]{n,p[1]+1});
					prev[n] = p[0];
				}
			}
		}
	}

	public ArrayList<Integer> getPath(int t,int[] prev){
		ArrayList<Integer> path = new ArrayList<Integer>();
		for(;t != -1;t = prev[t])path.add(t);
		Collections.reverse(path);
		return path;
	}

	@SuppressWarnings("unchecked")
	public void solve() {
		N = nextInt();
		u = nextInt()-1;
		v = nextInt()-1;

		G = new ArrayList[N];
		for(int i = 0;i < N;i++)G[i] = new ArrayList<Integer>();
		for(int i = 0;i < N-1;i++){
			int a = nextInt()-1;
			int b = nextInt()-1;
			G[a].add(b);
			G[b].add(a);
		}

		if(N % 2 == 1){
			out.println("No");
			return;
		}
		int[] dis1 = new int[N],dis2 = new int[N];
		prev1 = new int[N];
		prev2 = new int[N];
		dijkstra(u,dis1,prev1);
		dijkstra(v,dis2,prev2);

		ArrayList<Integer> du = new ArrayList<Integer>(),dv = new ArrayList<Integer>();
		for(int i = 0;i < N;i++){
			if(dis1[i] == N/2)du.add(i);
			if(dis2[i] == N/2)dv.add(i);
		}

		if(du.size() == 0 || dv.size() == 0){
			out.println("No");
			return;
		}
		boolean[] used = new boolean[N];
		for(int i = 0;i < du.size();i++){
			for(int j = 0;j < dv.size();j++){
				Arrays.fill(used, false);

				for(int n : getPath(du.get(i),prev1)){
					used[n] = true;
				}
				boolean flag = true;
				for(int n : getPath(dv.get(j),prev2)){
					if(used[n]){
						flag = false;
						break;
					}
				}

				if(flag){
					out.println("Yes");
					return;
				}
			}
		}
		out.println("No");

	}

	public static void main(String[] args) {
		out.flush();
		new Main().solve();
		out.close();
	}

	/* Input */
	private static final InputStream in = System.in;
	private static final PrintWriter out = new PrintWriter(System.out);
	private final byte[] buffer = new byte[2048];
	private int p = 0;
	private int buflen = 0;

	private boolean hasNextByte() {
		if (p < buflen)
			return true;
		p = 0;
		try {
			buflen = in.read(buffer);
		} catch (IOException e) {
			e.printStackTrace();
		}
		if (buflen <= 0)
			return false;
		return true;
	}

	public boolean hasNext() {
		while (hasNextByte() && !isPrint(buffer[p])) {
			p++;
		}
		return hasNextByte();
	}

	private boolean isPrint(int ch) {
		if (ch >= '!' && ch <= '~')
			return true;
		return false;
	}

	private int nextByte() {
		if (!hasNextByte())
			return -1;
		return buffer[p++];
	}

	public String next() {
		if (!hasNext())
			throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		int b = -1;
		while (isPrint((b = nextByte()))) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}

	public int nextInt() {
		return Integer.parseInt(next());
	}

	public long nextLong() {
		return Long.parseLong(next());
	}

	public double nextDouble() {
		return Double.parseDouble(next());
	}
}