結果

問題 No.2337 Equidistant
ユーザー fgwiebfaoishfgwiebfaoish
提出日時 2023-06-03 13:07:12
言語 C#(csc)
(csc 3.9.0)
結果
AC  
実行時間 1,545 ms / 4,000 ms
コード長 9,662 bytes
コンパイル時間 3,769 ms
コンパイル使用メモリ 115,376 KB
実行使用メモリ 77,984 KB
最終ジャッジ日時 2023-08-28 07:48:05
合計ジャッジ時間 25,840 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 61 ms
21,100 KB
testcase_01 AC 60 ms
23,076 KB
testcase_02 AC 62 ms
21,108 KB
testcase_03 AC 61 ms
19,104 KB
testcase_04 AC 63 ms
23,096 KB
testcase_05 AC 62 ms
21,096 KB
testcase_06 AC 68 ms
23,092 KB
testcase_07 AC 67 ms
21,096 KB
testcase_08 AC 67 ms
21,148 KB
testcase_09 AC 67 ms
23,144 KB
testcase_10 AC 66 ms
21,164 KB
testcase_11 AC 1,017 ms
65,272 KB
testcase_12 AC 996 ms
67,388 KB
testcase_13 AC 978 ms
65,364 KB
testcase_14 AC 986 ms
65,388 KB
testcase_15 AC 970 ms
67,424 KB
testcase_16 AC 1,030 ms
65,340 KB
testcase_17 AC 1,028 ms
67,500 KB
testcase_18 AC 1,004 ms
65,372 KB
testcase_19 AC 1,043 ms
67,356 KB
testcase_20 AC 1,000 ms
67,372 KB
testcase_21 AC 1,075 ms
77,984 KB
testcase_22 AC 863 ms
68,064 KB
testcase_23 AC 951 ms
69,312 KB
testcase_24 AC 1,393 ms
73,776 KB
testcase_25 AC 1,003 ms
69,348 KB
testcase_26 AC 1,545 ms
73,600 KB
testcase_27 AC 1,012 ms
71,124 KB
testcase_28 AC 1,003 ms
71,120 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
Microsoft (R) Visual C# Compiler version 3.9.0-6.21124.20 (db94f4cc)
Copyright (C) Microsoft Corporation. All rights reserved.

ソースコード

diff # 

using System;
using System.Collections.Generic;
using System.Collections;
using System.Collections.Specialized;
using System.Linq;
using System.Text;
using System.IO;
using System.Reflection;
using static System.Math;
using System.Numerics;
using System.Threading;
using System.Runtime.CompilerServices;
using System.Diagnostics;
static class Program {
	const long inf = long.MaxValue>>1;
	const int mod = 998244353;
	static Sc sc = new Sc();
	static void Main() {
		Pt pt = new Pt(Solve);
		pt.Sm();
	}
	static void Solve(Pt pt) {
		var (n,q)=sc.Tp2<int>();
		var m = n-1;
		var li = new List<int>[n+1];
		for(int i = 1;i<=n;i++) { li[i]=new List<int>(); }
		for(int i = 0;i<m;i++) {
			var e = sc.Ia;
			li[e[0]].Add(e[1]);
			li[e[1]].Add(e[0]);
		}
		var da = new Dlca(li,true);
		for(int i = 0;i<q;i++) {
			var e = sc.Ia;
			var di = da.Di(e[0],e[1]);
			if((di&1)==0) {
				var c = 0;
				int ans = 0;
				if(da.de[e[0]]==da.de[e[1]]) {
					ans=n-da.cd[da.Rt(e[0],(di>>1)-1)]-da.cd[da.Rt(e[1],(di>>1)-1)];
				}
				else if(da.de[e[0]]>da.de[e[1]]) {
					c=da.Rt(e[0],di>>1);
					ans=da.cd[c]-da.cd[da.Rt(e[0],(di>>1)-1)];
				}
				else {
					c=da.Rt(e[1],di>>1);
					ans =da.cd[c]-da.cd[da.Rt(e[1],(di>>1)-1)];
				}
				pt.Wl(ans);
			}
			else {
				pt.Wl(0);
			}
		}
	}
}
public class Dlca {
	private bool[] b;
	private int[][] h;
	public readonly int[] de;
	private int o;
	private List<int>[] li;
	public readonly List<int> pe;
	public readonly int[] pa;
	public readonly int[] cd;
	public Dlca(List<int>[] li,int pe) {
		this.li=li;
		int n = li.Length;
		o=(int)Log(n-1,2)+1;
		de=new int[n];
		de[0]=-1;
		h=new int[o][];
		b=new bool[n];
		h[0]=new int[n];
		pa=new int[n];
		cd=new int[n];
		this.pe=new List<int>();
		if(pe!=-1) {
			Fd1(pe,0,pe);
			this.pe.Add(pe);
		}
		else {
			for(int i = 1;i<n;i++) {
				if(!b[i]) {
					Fd1(i,0,i);
					this.pe.Add(i);
				}
			}
		}
		for(int i = 1;i<o;i++) {
			h[i]=new int[n];
			for(int j = 1;j<n;j++) { h[i][j]=h[i-1][h[i-1][j]]; }
		}
	}
	public Dlca(List<int>[] li,bool bo) : this(li,bo ? 1 : -1) { }
	private void Fd1(int a,int f,int p) {
		b[a]=true;
		de[a]=f;
		pa[a]=p;
		cd[a]=1;
		for(int i = 0;i<li[a].Count;i++) {
			int j = (int)(object)li[a][i];
			if(!b[j]) {
				h[0][j]=a;
				Fd1(j,f+1,p);
				cd[a]+=cd[j];
			}
		}
	}
	public int Lca(int a,int b) {
		if(de[a]>de[b]) { int c = a; a=b; b=c; }
		for(int i = o-1;de[a]!=de[b];i--) { if(de[h[i][b]]>=de[a]) { b=h[i][b]; } }
		if(a==b) { return a; }
		for(int i = o-1;i>=0;i--) { if(h[i][a]!=h[i][b]) { a=h[i][a]; b=h[i][b]; } }
		return h[0][a];
	}
	public int Di(int a,int b) {
		int l = Lca(a,b);
		return l!=0 ? de[a]+de[b]-(de[l]<<1) : int.MinValue;
	}
	public int Rt(int a,int b) {
		if((b&~((1<<h.Length)-1))!=0) return 0;
		for(int i = 0;i<h.Length;i++) {
			if((b&(1<<i))!=0) { a=h[i][a]; }
		}
		return a;
	}
}
public class Pt {
	private StringBuilder sb = new StringBuilder();
	public Pt(Action<Pt> f) { f(this); }
	public void W(int s) { sb.Append(s); }
	public void W(long s) { sb.Append(s); }
	public void W(double s) { sb.Append(s); }
	public void W(decimal s) { sb.Append(s); }
	public void W(char s) { sb.Append(s); }
	public void W(string s) { sb.Append(s); }
	public void W(object s) { sb.Append(s); }
	public void W(params object[] s) { sb.Append(string.Join(" ",s)); }
	public void Wl(int s) { sb.Append(s).Append(Environment.NewLine); }
	public void Wl(long s) { sb.Append(s).Append(Environment.NewLine); }
	public void Wl(double s) { sb.Append(s).Append(Environment.NewLine); }
	public void Wl(decimal s) { sb.Append(s).Append(Environment.NewLine); }
	public void Wl(char s) { sb.Append(s).Append(Environment.NewLine); }
	public void Wl(string s) { sb.Append(s).Append(Environment.NewLine); }
	public void Wl(object s) { sb.Append(s).Append(Environment.NewLine); }
	public void Wl(int[] s) { sb.Append(string.Join(" ",s)).Append(Environment.NewLine); }
	public void Wl(long[] s) { sb.Append(string.Join(" ",s)).Append(Environment.NewLine); }
	public void Wl(double[] s) { sb.Append(string.Join(" ",s)).Append(Environment.NewLine); }
	public void Wl(string[] s) { sb.Append(string.Join(" ",s)).Append(Environment.NewLine); }
	public void Wl(params object[] s) { sb.Append(string.Join(" ",s)).Append(Environment.NewLine); }
	public void Wl() { sb.Append(Environment.NewLine); }
	public void Sm() { Console.Write(sb); }
	public void Op(StreamWriter sw) {
		sw.Write(sb);
		sw.Close();
	}
	public static bool operator ==(Pt a,Pt b) { return a.sb.ToString()==b.sb.ToString(); }
	public static bool operator !=(Pt a,Pt b) { return a.sb.ToString()!=b.sb.ToString(); }
	public override bool Equals(object obj) { return false; }
	public override int GetHashCode() { return 0; }
}
public class Sc {
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	protected virtual string Rl() { return Console.ReadLine(); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	protected virtual string[] Sp(string st) { return st.Split(); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	private T Ct<T>(string s) { return (T)Convert.ChangeType(s,typeof(T)); }
	public virtual int I { get { return int.Parse(Rl()); } }
	public virtual long L { get { return long.Parse(Rl()); } }
	public virtual double D { get { return double.Parse(Rl()); } }
	public virtual string S { get { return Rl(); } }
	public int[] Ia { get { return Array.ConvertAll(Sp(Rl()),int.Parse); } }
	public long[] La { get { return Array.ConvertAll(Sp(Rl()),long.Parse); } }
	public double[] Da { get { return Array.ConvertAll(Sp(Rl()),double.Parse); } }
	public string[] Sa { get { return Sp(Rl()); } }
	public object[] Oa { get { return Sp(Rl()); } }
	public int[] Ia2 { get { return Array.ConvertAll(Sp("0 "+Rl()+" 0"),int.Parse); } }
	public int[] Ia3(string a,string b) { return Array.ConvertAll(Sp(a+Rl()+b),int.Parse); }
	public int[] Ia3(int a) { return Array.ConvertAll(Sp(Rl()+" "+a.ToString()),int.Parse); }
	public long[] La2 { get { return Array.ConvertAll(Sp("0 "+Rl()+" 0"),long.Parse); } }
	public long[] La3(string a,string b) { return Array.ConvertAll(Sp(a+Rl()+b),long.Parse); }
	public long[] La3(int a) { return Array.ConvertAll(Sp(Rl()+" "+a.ToString()),long.Parse); }
	public double[] Da2 { get { return Array.ConvertAll(Sp("0 "+Rl()+" 0"),double.Parse); } }
	public double[] Da3(string a,string b) { return Array.ConvertAll(Sp(a+Rl()+b),double.Parse); }
	public T[] Arr<T>(int n,Func<T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(); } return a; }
	public T[] Arr<T>(int n,Func<int,T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(i); } return a; }
	public T[] Arr<T>(int n,Func<string[],T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(Sp(Rl())); } return a; }
	public T[] Arr<T>(int n,Func<int,string[],T> f) { var a = new T[n]; for(int i = 0;i<n;i++) { a[i]=f(i,Sp(Rl())); } return a; }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T, T) Tp2<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T, T, T) Tp3<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T, T, T, T) Tp4<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2]), Ct<T>(s[3])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T, T, T, T, T) Tp5<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2]), Ct<T>(s[3]), Ct<T>(s[4])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T, T, T, T, T, T) Tp6<T>() { var s = Sp(Rl()); return (Ct<T>(s[0]), Ct<T>(s[1]), Ct<T>(s[2]), Ct<T>(s[3]), Ct<T>(s[4]), Ct<T>(s[5])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T1, T2) Tp2<T1, T2>() { var s = Sp(Rl()); return (Ct<T1>(s[0]), Ct<T2>(s[1])); }
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	public (T1, T1, T2) Tp3<T1, T2>() { var s = Sp(Rl()); return (Ct<T1>(s[0]), Ct<T1>(s[1]), Ct<T2>(s[2])); }
}
public class Scr:Sc {
	private List<string> li = new List<string>();
	private int l = 0;
	private bool bo = false;
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	protected override string Rl() {
		if(bo) { return li[l++%li.Count]; }
		li.Add(Console.ReadLine());
		return li[li.Count-1];
	}
	public void Again() { bo=true; }
}
public class Sc2:Sc {
	private string[] sps = new string[] { " ","　","\t" };
	[MethodImpl(MethodImplOptions.AggressiveInlining)]
	protected override string[] Sp(string st) { return st.Split(sps,StringSplitOptions.RemoveEmptyEntries); }
	public override int I { get { return int.Parse(Sp(Rl())[0]); } }
	public override long L { get { return long.Parse(Sp(Rl())[0]); } }
	public override double D { get { return double.Parse(Sp(Rl())[0]); } }
	public override string S { get { return Sp(Rl())[0]; } }
}
public class Sct:Sc {
	private List<string> li = new List<string>();
	private int l = 0;
	public void Add(int s) { li.Add(s.ToString()); }
	public void Add(long s) { li.Add(s.ToString()); }
	public void Add(double s) { li.Add(s.ToString()); }
	public void Add(string s) { li.Add(s.ToString()); }
	public void Add(object s) { li.Add(s.ToString()); }
	public void Add(int[] s) { li.Add(string.Join(" ",s)); }
	public void Add(long[] s) { li.Add(string.Join(" ",s)); }
	public void Add(double[] s) { li.Add(string.Join(" ",s)); }
	public void Add(string[] s) { li.Add(string.Join(" ",s)); }
	public void Add(object[] s) { li.Add(string.Join(" ",s)); }
	protected override string Rl() { return li[l++]; }
	public void Clear() { li.Clear(); l=0; }
	public void Again() { l=0; }
	public void Pf() { Console.WriteLine(string.Join("\n",li)); }
}
0