[原创]codefoces #364 div2 E &&div 1 B Connecting Universities [图论]【求贡献】

2016-07-28 20:39:58 Tabris_ 阅读数：592

博客爬取于2020-06-14 22:44:04
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/52058872

题目连接 ：http://codeforces.com/problemset/problem/700/B

CF 的题目 可以去VJ上 挂

---------------------------------------------------------.

Connecting Universities
time limit per test3 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
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.

Input
The first line of the input contains two integers n and k (2 ≤ n ≤ 200 000, 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 u1, u2, …, u2k (1 ≤ ui ≤ 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 xj and yj (1 ≤ xj, yj ≤ n), which means that the j-th road connects towns xj and yj. All of them are two-way roads. You can move from any town to any other using only these roads.

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

Examples
input
7 2
1 5 6 2
1 3
3 2
4 5
3 7
4 3
4 6
output
6
input
9 3
3 2 1 6 5 9
8 9
3 2
2 7
3 4
7 6
4 5
2 1
2 8
output
9
Note
The figure below shows one of possible division into pairs in the first test. If you connect universities number 1 and 6 (marked in red) and universities number 2 and 5 (marked in blue) by using the cable, the total distance will equal 6 which will be the maximum sum in this example.
这里写图片描述

---------------------------------------------------------.

题目大意 ：就是让你找在K*2个点中找到K条路 使得和最大

解题思路
其实把每条路都求出来在加和的话 一定会超时 所以要换一种思路 看了一下node 发现总是有那么多的边被很多路经过
所以就求出来每条边被多少路经过就行了呗
而求被多少条路经过就简单多了 只有求出这条路径左边有多少个k2里的点右边边有多少个k2里的点 取小的那一个值就行了
这是必然的 想让路最长对于每一条边来说 一定是让左右两边的点尽可能的连上
最终记录下来每条边对总结过的贡献就行了 总复杂度O（N）
这种贡献式思维 很常用 也很好用 能大大降低时间复杂度 而且在很多时候比直接求解的代码 算法上的难度要小 而且小很多

附本题代码

-----------------------------------------------------.

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
# include <iostream>
# include <stdio.h>
# include <algorithm>
# include <math.h>
# include <string>
# include <string.h>
# include <vector>
using namespace std;

# define LL __int64
# define INF 0x1f1f1f1f


/*************************************/
# define pb push_back


int has[202020],ha[202020];
vector<int>pr[202020];
int num[202020];
LL ans = 0;

int dfs(int u,int v,int &k)  // v是代表这条边的上一条边连接的是谁
{
    ha[u]=1;
    if(has[u]) num[u]++;

    int Mi = 0;

    for(int i=0;i<pr[u].size();i++)
    {
        if(pr[u][i]==v) continue;

        dfs(pr[u][i],u,k); // 继续顺着下一个连接的边搜下去  这样最后搜到叶子节点才会返回并记录数值 确保不会落下那条边与点

        Mi += num[pr[u][i]];
        ans += min(2*k-num[pr[u][i]],num[pr[u][i]]);  //计数很好理解
    }
    num[u] += Mi;
}

int main()
{

    memset(has,0,sizeof(has));
    memset(num,0,sizeof(num));

    int n,k;
    scanf("%d%d",&n,&k);

    int x;
    for(int i=0;i<k*2;i++)
    {
        scanf("%d",&x);
        has[x]=1;
    }

    int u,v;
    for(int i=1;i<n;i++)
    {
        scanf("%d%d",&u,&v);//看到这里就知道为什么一定要用vector了吧  如果不 就一定会爆内存  而vector下最坏也只是4e5

        pr[u].pb(v);
        pr[v].pb(u);
    }

    for(int i=1;i<=n;i++)
        if(!ha[i]&&has[i])//搜索没搜索过得点  被搜过就不需要在搜一遍了
            dfs(1,-1,k);

    printf("%I64d\n",ans);

    return 0;
}