← 返回题目列表

AtCoder · abc014_4

D. 循环

中文机器翻译题面 查看原题

問題文

n 顶点和 n-1 给出了由书边组成的连通无向图。在每个顶点 1 它们的编号最大为 n 之前的数字按顺序编号。

在图论中,满足这些条件的图称为树,并且具有不包含环的性质。 对于该图,添加原始图中未包含的附加边。 如果我们考虑一张添加了一个 (a,b) 的图,则该图恰好包含一个循环。 您的任务是打印此类图的循环长度(循环中包含的边数)。然而,有几个附加边缘的候选者, 给出了Q ,因此请输出所有这些的答案。


入力

输入是按以下格式从标准输入给出的。

N
x_1\ y_1
x_2\ y_2
:
x_{N-1}\ y_{N-1}
Q
a_1\ b_1
a_2\ b_2
:
a_{Q}\ b_{Q}
  • 1 行包含一个表示图中顶点数的整数。 给出了 N (1≦N≦100,000) 。
  • 继续2 从行N-1行表示图的边缘信息。 第i行显示由边连接的顶点。 x_i 和 y_i用空格分隔。
  • 继续1+N 边缘 一个整数,表示(a,b)的候选者数量 Q (1≦Q≦100,000) 。
  • 继续2+N 从行Q行是 表示有关第i个附加边缘候选的信息。i 行显示由附加边连接的顶点。 a_i 和 b_i用空格分隔。
  • 所有给定的边都连接现有的顶点。
  • 该图不包含自边。也就是说,任何 关于i,x_i≠y_i成立。
  • 该图不包含多条边。也就是说,任何i,j(i≠j),x_i≠x_j或y_i≠y_j成立。
  • 附加边是未包含在原始图中的边,并且保证不是自边。

部分点

这个问题有两个数据集,并且为每个数据集设置了部分点。 如果您对满足

  • Q=1 的数据集 1 的回答正确 给出 30 点。
  • 如果您在没有附加约束的情况下在数据集 2 中回答正确, 70 点。

出力

对于所有附加候选边,计算将它们添加到原始图中时创建的循环长度,1 从行 Q 按顺序输出各行。在输出末尾插入换行符。


入力例1

5
1 2
1 3
1 4
4 5
3
2 3
2 5
2 4

出力例1

3
4
3

示意图如下。


入力例2

6
1 2
2 3
3 4
4 5
5 6
4
1 3
1 4
1 5
1 6

出力例2

3
4
5
6

入力例3

7
3 1
2 1
2 4
2 5
3 6
3 7
5
4 5
1 6
5 6
4 7
5 3

出力例3

3
3
5
5
4