Paint the Tree

题面翻译

378QAQ 有一棵树，其顶点有 $n$ 个。最初，所有顶点都是白色的。

树上有两个棋子，分别称为 $P_A$ 和 $P_B$ 。 $P_A$ 和 $P_B$ 最初分别位于顶点 $a$ 和 $b$ 上。在每一步中，378QAQ 将按顺序执行以下操作：

1. 将 $P_A$ 移动到相邻顶点。如果目标顶点是白色的，则该顶点将被涂成红色。

2. 将 $P_B$ 移动到相邻顶点。如果目标顶点是红色的，则该顶点将被涂成蓝色。

最初，顶点 $a$ 被涂成红色。如果 $a=b$ ，则顶点 $a$ 被涂成蓝色。请注意，每一步都必须移动两个棋子。两个棋子可以同时位于同一个顶点。

378QAQ 想知道将所有顶点涂成蓝色所需的最少步数。

题目描述

378QAQ has a tree with $ n $ vertices. Initially, all vertices are white.

There are two chess pieces called $ P_A $ and $ P_B $ on the tree. $ P_A $ and $ P_B $ are initially located on vertices $ a $ and $ b $ respectively. In one step, 378QAQ will do the following in order:

1. Move $ P_A $ to a neighboring vertex. If the target vertex is white, this vertex will be painted red.
2. Move $ P_B $ to a neighboring vertex. If the target vertex is colored in red, this vertex will be painted blue.

Initially, the vertex $ a $ is painted red. If $ a=b $ , the vertex $ a $ is painted blue instead. Note that both the chess pieces must be moved in each step. Two pieces can be on the same vertex at any given time.

378QAQ wants to know the minimum number of steps to paint all vertices blue.

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1\leq t\leq 10^4 $ ). The description of the test cases follows.

The first line of each test case contains one integer $ n $ ( $ 1\leq n\leq 2\cdot 10^5 $ ).

The second line of each test case contains two integers $ a $ and $ b $ ( $ 1\leq a,b\leq n $ ).

Then $ n - 1 $ lines follow, each line contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i,y_i \le n $ ), indicating an edge between vertices $ x_i $ and $ y_i $ . It is guaranteed that these edges form a tree.

It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .

输出格式

For each test case, output the minimum number of steps to paint all vertices blue.

样例 #1

样例输入 #1

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

样例输出 #1

2
8
13

提示

In the first test case, 378QAQ can paint all vertices blue in the following order:

• Initially, $ P_A $ is located on the vertex $ 1 $ , and $ P_B $ is located on the vertex $ 2 $ . The vertex $ 1 $ is painted red and the vertex $ 2 $ is white.
• 378QAQ moves $ P_A $ to the vertex $ 2 $ and paints it red. Then 378QAQ moves $ P_B $ to the vertex $ 1 $ and paints it blue.
• 378QAQ moves $ P_A $ to the vertex $ 1 $ . Then 378QAQ moves $ P_B $ to the vertex $ 2 $ and paints it blue.

最好的情况是先让他们重合，再一个一个走，当然对于他们重合的点来说的最长的那一条路最后走，这样最长的的只需要走一遍，不用再回来，而对于其他点，叶子节点走一遍，其余的走两遍，避免麻烦，我们设从重合的点开始走到叶子节点，再回到重合点时重合点算走了一遍，我们把重合的点走的那一遍算给叶子节点，这样除了重合的点走了0次，最长的路走一次，其他点都是两次，再加上他们重合所需要的步数，也有无法重合的情况，只要我们算他们最靠近时的a的点算重合点，最后的时候让b走多一次即可

const int N = 2e5 + 10;
int e[N * 2], ne[N * 2], h[N], idx;
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx++;
}
int aa[N], bb[N], zx[N];
void dfsa(int x,int fa,int se)
{
    aa[x] = se;
    se++;
    for (int i = h[x]; i!=-1; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfsa(j, x, se);
    }
}
void dfsb(int x, int fa, int se)
{
    bb[x] = se;
    se++;
    for (int i = h[x]; i!=-1; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfsb(j, x, se);
    }
}
void dfsg(int x, int fa, int se)
{
    zx[x] = se;
    se++;
    for (int i = h[x]; i!=-1; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;
        dfsg(j, x, se);
    }
}
void solve()
{
    memset(h, -1, sizeof(h));
    int n;
    cin >> n;
    int a, b;
    cin >> a >> b;
    for (int i = 1; i <= n - 1; i++)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
        add(y, x);
    }
    dfsa(a,0,0);
    dfsb(b,0,0);
    int ge = 1e9;
    int zhi = 1e9;
    int bu = 0;
    int ok = 0;
    for (int i = 1; i <= n; i++)
    {
        if(aa[i]==bb[i]&&aa[i]<zhi)
        {
            zhi = aa[i];
            ge = i;
        }
    }

    if (ge != 1e9) bu = aa[ge];
    else
    {
        ok = 1;
        for (int i = 1; i <= n; i++)
        {
            if (aa[i] == bb[i] - 1 && aa[i] < zhi)
            {
                zhi = aa[i];
                ge = i;
            }
        }
        bu = aa[ge];
    }
    dfsg(ge, 0, 0);
    int yuan = 0;
    for (int i = 1; i <= n; i++) yuan = max(yuan, zx[i]);
    if(ok==1)  cout << 2 * n - yuan - 2 + bu + 1 << '\n';
    else  cout << 2 * n - yuan - 2 + bu << '\n';
    idx = 0;
}