oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

closedpath Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

closedpath.html

closedpath

Problem Statement

You are given an undirected, connected graph with N vertices numbered from 1 to N and N-1 edges, with the ith edge connecting vertices (xi,yi). In graph theory language, such a graph is called a tree, and it has the property that there does not exist a cycle in this graph. If we add an edge to this graph, a single cycle is formed. There are Q candidate edges we want to add, the jth one connecting (ai,bi). For each of the Q queries, output the length of the cycle when this edge is added to the graph. Note that each of the Q queries are independed of each other, and that no edges are actually added to the graph.

Constraints

  • 1 ≤ N ≤ 105
  • 1 ≤ Q ≤ 105
  • 1 ≤ xi, yi, aj, bj ≤ N
  • For all i, xi ≠ yi
  • For all i ≠ j, (xi,yi) ≠ (xj,yj)
  • For all i, j, (xi,yi) ≠ (aj,bj)
  • The given graph forms a tree.

Partial Scores

  • In the test set worth 30 points, Q = 1.

Input

Input is given from Standard Input in the following format:

N
x1 y1
x2 y2
:
xN-1 yN-1
Q
a1 b1
a2 b2
:
aQ bQ

Output

For each of the Q queries, output a single integer, the length of the cycle when the corresponding edge is added to the graph.

Sample Input 1

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

Sample Output 1

3
4
3

Sample Input 2

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

Sample Output 2

3
4
5
6

Sample Input 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

Sample Output 3

3
3
5
5
4

Tags

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
130101s256MBMinimum
270351s256MBMinimum
3031s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o closedpath -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.