Submission #989567
Source Code Expand
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;
using System.Threading;
using Pair = System.Collections.Generic.KeyValuePair<int, int>;
class Program
{
public Program() { }
static void Main(string[] args)
{
new Program().prog();
}
Scanner cin;
const int MOD = 1000000007;
const int INF = int.MaxValue - 10;
const long INFL = long.MaxValue - 10;
const double EPS = 1e-7;
const double PI = 3.1415926536;
int N;
List<int>[] G;
int[] vs, depth, id;
int root = 0;
SegTreeMinIndex seg;
void prog()
{
cin = new Scanner();
int[,] dir8 = new int[8, 2] { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } };
int[,] dir4 = new int[4, 2] { { -1, 0 }, { 0, -1 }, { 0, 1 }, { 1, 0 } };
N = cin.nextInt();
G = new List<int>[N];
for (int i = 0; i < N; i++)
{
G[i] = new List<int>();
}
for (int i = 0; i < N-1; i++)
{
int x = cin.nextInt() - 1;
int y = cin.nextInt() - 1;
G[x].Add(y);
G[y].Add(x);
}
vs = new int[2 * N - 1];
depth = new int[2 * N - 1];
id = new int[N];
init();
int[] depth_id = new int[N];
for (int i = 0; i < 2*N-1; i++)
{
depth_id[vs[i]] = depth[i];
}
int Q = cin.nextInt();
for (int i = 0; i < Q; i++)
{
int a = cin.nextInt() - 1;
int b = cin.nextInt() - 1;
int c = lca(a, b);
Console.WriteLine(depth_id[a] + depth_id[b] - 2 * depth_id[c] + 1);
}
}
void dfs(int v, int parent, int d, ref int k)
{
id[v] = k;
vs[k] = v;
depth[k++] = d;
for (int i = 0; i < G[v].Count; i++)
{
if (G[v][i] != parent)
{
dfs(G[v][i], v, d + 1, ref k);
vs[k] = v;
depth[k++] = d;
}
}
}
// 初期化
void init()
{
int k = 0;
dfs(root, -1, 0, ref k);
// RMQを初期化する(最小値ではなく、最小値のインデックスを返すようにする)
seg = new SegTreeMinIndex(depth);
}
int lca(int u, int v)
{
return vs[seg.rmq(Math.Min(id[u], id[v]), Math.Max(id[u], id[v]) + 1)];
}
class SegTreeMinIndex
{
int n; // 葉ノードの数
int[] dat;
int[] minIndex;
// 区間[a,b)の最小値。ノードk=[l,r)に着目している。
public Pair _rmq(int a, int b, int k, int l, int r)
{
if (r <= a || b <= l) return new Pair(INF, -1); // 交差しない
if (a <= l && r <= b) return new Pair(dat[k], minIndex[k]); //a,l,r,bの順
else {
Pair s1 = _rmq(a, b, 2 * k + 1, l, (l + r) / 2);
Pair s2 = _rmq(a, b, 2 * k + 2, (l + r) / 2, r);
if (s1.Key < s2.Key)
{
return s1;
}
else
{
return s2;
}
}
}
public int rmq(int a, int b)
{
return _rmq(a, b, 0, 0, n).Value;
}
public void update(int k, int x)
{
k += n - 1;
dat[k] = x;
while (k > 0)
{
k = (k - 1) / 2;
if (dat[k * 2 + 1] < dat[k * 2 + 2])
{
dat[k] = dat[k * 2 + 1];
minIndex[k] = minIndex[k * 2 + 1];
}
else
{
dat[k] = dat[k * 2 + 2];
minIndex[k] = minIndex[k * 2 + 2];
}
}
}
public SegTreeMinIndex(int size)
{
n = 1;
while (n < size) n <<= 1;
dat = new int[2 * n - 1];
minIndex = new int[2 * n - 1];
}
public SegTreeMinIndex(int[] array)
{
n = 1;
while (n < array.Length) n <<= 1;
dat = new int[2 * n - 1];
minIndex = new int[2 * n - 1];
for (int i = 0; i < array.Length; i++)
{
dat[i + n - 1] = array[i];
minIndex[i + n - 1] = i;
}
for (int i = array.Length; i < n; i++)
{
dat[i + n - 1] = INF;
minIndex[i + n - 1] = i;
}
for (int i = n - 2; i >= 0; i--)
{
if (dat[i * 2 + 1] < dat[i * 2 + 2])
{
dat[i] = dat[i * 2 + 1];
minIndex[i] = minIndex[i * 2 + 1];
}
else
{
dat[i] = dat[i * 2 + 2];
minIndex[i] = minIndex[i * 2 + 2];
}
}
}
}
}
class Scanner
{
string[] s;
int i;
char[] cs = new char[] { ' ' };
public Scanner()
{
s = new string[0];
i = 0;
}
public string next()
{
if (i < s.Length) return s[i++];
string st = Console.ReadLine();
while (st == "") st = Console.ReadLine();
s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
i = 0;
return next();
}
public int nextInt()
{
return int.Parse(next());
}
public long nextLong()
{
return long.Parse(next());
}
public double nextDouble()
{
return double.Parse(next());
}
}
Submission Info
Submission Time |
|
Task |
D - 閉路 |
User |
furuya1223 |
Language |
C# (Mono 2.10.8.1) |
Score |
100 |
Code Size |
4587 Byte |
Status |
AC |
Exec Time |
1306 ms |
Memory |
35180 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt |
Subtask1 |
subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt |
Subtask2 |
subtask0_sample01.txt, subtask0_sample02.txt, subtask0_sample03.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt |
Case Name |
Status |
Exec Time |
Memory |
subtask0_sample01.txt |
AC |
62 ms |
4064 KB |
subtask0_sample02.txt |
AC |
62 ms |
4076 KB |
subtask0_sample03.txt |
AC |
60 ms |
4088 KB |
subtask1_01.txt |
AC |
185 ms |
28692 KB |
subtask1_02.txt |
AC |
184 ms |
28676 KB |
subtask1_03.txt |
AC |
61 ms |
4072 KB |
subtask1_04.txt |
AC |
60 ms |
4076 KB |
subtask1_05.txt |
AC |
63 ms |
4368 KB |
subtask1_06.txt |
AC |
63 ms |
4324 KB |
subtask1_07.txt |
AC |
208 ms |
23296 KB |
subtask1_08.txt |
AC |
205 ms |
23408 KB |
subtask1_09.txt |
AC |
198 ms |
23292 KB |
subtask1_10.txt |
AC |
204 ms |
23296 KB |
subtask1_11.txt |
AC |
205 ms |
23296 KB |
subtask1_12.txt |
AC |
199 ms |
23296 KB |
subtask2_01.txt |
AC |
1043 ms |
35180 KB |
subtask2_02.txt |
AC |
1153 ms |
35128 KB |
subtask2_03.txt |
AC |
911 ms |
4336 KB |
subtask2_04.txt |
AC |
939 ms |
4348 KB |
subtask2_05.txt |
AC |
942 ms |
4476 KB |
subtask2_06.txt |
AC |
980 ms |
4408 KB |
subtask2_07.txt |
AC |
1292 ms |
28288 KB |
subtask2_08.txt |
AC |
1283 ms |
28156 KB |
subtask2_09.txt |
AC |
1300 ms |
28160 KB |
subtask2_10.txt |
AC |
1291 ms |
28188 KB |
subtask2_11.txt |
AC |
1276 ms |
28156 KB |
subtask2_12.txt |
AC |
1306 ms |
28136 KB |