CF700B-Connecting Universities

题目:

题目描述:

Treeland is a country in which there are $ n $ towns connected by $ n-1 $ two-way road such that it’s possible to get from any town to any other town.

In Treeland there are $ 2k $ universities which are located in different towns.

Recently, the president signed the decree to connect universities by high-speed network.The Ministry of Education understood the decree in its own way and decided that it was enough to connect each university with another one by using a cable. Formally, the decree will be done!

To have the maximum sum in the budget, the Ministry decided to divide universities into pairs so that the total length of the required cable will be maximum. In other words, the total distance between universities in $ k $ pairs should be as large as possible.

Help the Ministry to find the maximum total distance. Of course, each university should be present in only one pair. Consider that all roads have the same length which is equal to $ 1 $ .

输入格式:

The first line of the input contains two integers $ n $ and $ k $ ( $ 2<=n<=200000 $ , $ 1<=k<=n/2 $ ) — the number of towns in Treeland and the number of university pairs. Consider that towns are numbered from $ 1 $ to $ n $ .

The second line contains $ 2k $ distinct integers $ u_{1},u_{2},…,u_{2k} $ ( $ 1<=u_{i}<=n $ ) — indices of towns in which universities are located.

The next $ n-1 $ line contains the description of roads. Each line contains the pair of integers $ x_{j} $ and $ y_{j} $ ( $ 1<=x_{j},y_{j}<=n $ ), which means that the $ j $ -th road connects towns $ x_{j} $ and $ y_{j} $ . All of them are two-way roads. You can move from any town to any other using only these roads.

输出格式:

Print the maximum possible sum of distances in the division of universities into $ k $ pairs.

样例:

样例输入 1:

1
2
3
4
5
6
7
8

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

样例输出 1:

1

6

样例输入 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

样例输出 2:

1

9

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

#include "ybwhead/ios.h"
const int maxn = 2e5 + 10;
vector<int> v[maxn];
int a[maxn];
long long ans;
int n, k;
void dfs(int u, int fa)
{
    for (int i = 0; i < v[u].size(); i++)
    {
        int vv = v[u][i];
        if (vv == fa)
            continue;
        dfs(vv, u);
        a[u] += a[vv];
        ans += min(a[vv], k * 2 - a[vv]);
    }
}
int main()
{
    yin >> n >> k;
    for (int i = 1; i <= k << 1; i++)
    {
        int x;
        yin >> x;
        a[x] = 1;
    }
    for (int i = 1; i < n; i++)
    {
        int x, y;
        yin >> x >> y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1, 0);
    yout << ans << endl;
    return 0;
}