Codeforces Round #364 (Div. 1) 700B(树)

题目大意

在n颗结点的树上有2k个需要配对的点，把他们两两配对，使得路程和最大并输出

选取一个点v

lv表示v与父亲的边

那么考虑lv被经过的次数，对于一个最大的情况，lv应该为min(sv, 2*k - sv) ，其中sv是v子树中需要配对的点（包括v）

假如lv比这个值小，那么必定有a和b在v的子树外，c和d在子树内，它们分别配对

但是如果这样的话，让a和c配对，b和d配对，显然更优

所以lv只能等于min(sv, 2*k - sv)

最后输出所有点的这个值的和即可

#include <iostream>

#include <cstdio>

#include <vector>

using namespace std;

long long sz[], ans;

vector <int> G[];

void dfs(int x, int fa)

{

    for(int i = ; i < G[x].size(); i++)

    {

        int to = G[x][i];

        if(to == fa) continue;

        dfs(to, x);

        sz[x] += sz[to];

    }

}

int n, k, x, y;

int main()

{

    cin>>n>>k;

    for(int i = ; i <= *k; i++) cin>>x, sz[x]++;

    for(int i = ; i < n; i++)

    {

        cin>>x>>y;

        G[x].push_back(y);

        G[y].push_back(x);

    }

    dfs(, );

    for(int i = ; i <= n; i++) ans += min(sz[i], *k - sz[i]);

    cout<<ans<<endl;

}