14084: 【原4084】千岛樱

题目

题目描述

author: Evensgn and LittleRound 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4084

题目描述

「真的是漂亮的樱花呢」
一位姑娘向你搭话道。
「那棵樱树，名字叫做“千岛樱”噢」

你的面前是一棵樱花树.

所谓树，指的是 \(n\) 个节点由 \(n - 1\) 条边连接起来，使得任意两个节点之间都联通.

这棵树的 \(n\) 个节点中，有 \(2k\) 个节点上 各有一朵 樱花.

众所周知，樱花之间需要相互交流才能有愉悦的心情，于是它们请你设计一个交流方案.

你注意到，樱花的数目是 \(2k\) 朵，是一个和谐的偶数，因此你决定将樱花分成 \(k\) 对，让它们进行一对一的交流.

同样众所周知的是，一朵樱花如果和距离它越远的另一朵樱花交流，它的心情就越愉快.

这里，两朵樱花之间距离指的是它们所在的两个节点在树上的最短路径的长度，每一条边的长度都是 \(1\).

请你安排一个将樱花们分为 \(k\) 对的方案，使得每对樱花之间距离的和最大.

即求 \(\max \sum_{i = 1}^{k} (第 i 对樱花之间的距离)\).

「听说是每秒五厘米」
「哦，什么？」
「樱花飘落的速度...」

「听说可能会超时呢」
「哦，什么？」
「如果用 cin 读入却不关同步的话...」

输入格式

输入的第一行有两个整数 \(n\) 和 \(k\).其中 \(n\) 是樱花树的节点数，这 \(n\) 个节点依次编号为 \(1\) 到 \(n\). \(k\) 为樱花数目的一半.

输入的第二行是 \(2k\) 个整数，分别表示 \(2k\) 朵樱花所在的节点编号.

输入接下来有 \(n - 1\) 行，每行 \(2\) 个整数 \(a_j\) 和 \(b_j\)，表示第 \(j\) 条边连接 \(a_j\) 和 \(b_j\) 这两个节点.

输出格式

输出一个整数，表示每对樱花之间距离的和的最大值.

样例输入 1

样例输出 1

样例输入 2

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

数据规模

对于 \(20%\) 的数据，\(1 \le n \le 10\).
对于 \(60%\) 的数据，\(1 \le n \le 1000\).
对于 \(100%\) 的数据，\(1 \le n \le 500000, \quad 2 \le 2k \le n\).

FineArtz's solution

/* 千岛樱 */
#include <iostream>
#include <vector>
using namespace std;

class Node{
public:
    int sub = 0;
    int father = 0;
    vector<int> child;
};

Node a[500005];
bool sa[500005] = {0};
int n, k;
long long ans = 0;

void makeTree(int x){
    if (sa[x]) a[x].sub = 1;
    for (auto i : a[x].child){
        if (i != a[x].father){
            a[i].father = x;
            makeTree(i);
            a[x].sub += a[i].sub;
        }
    }
    return;
}
void countDis(int x){
    for (auto i : a[x].child){
        if (i != a[x].father){
            ans += min(a[i].sub, 2 * k - a[i].sub);
            countDis(i);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= 2 * k; ++i){
        int x;
        cin >> x;
        sa[x] = true;
    }
    for (int i = 1; i <= n - 1; ++i){
        int x, y;
        cin >> x >> y;
        a[x].child.push_back(y);
        a[y].child.push_back(x);
    }
    makeTree(1);
    countDis(1);
    cout << ans << endl;
    return 0;
}

WashSwang's solution

#include <iostream>
#include <cstdio>
using namespace std;
int num,maxl,x,y,last[510000],nxt[1010000],to[1010000],son[510000],n,k;
bool vis[510000];
void add(int x,int y){
    to[++num]=y;
    nxt[num]=last[x];
    last[x]=num;
}
void dfs(int x){
    int y;
    vis[x]=true;
    for (int i=last[x];i!=0;i=nxt[i])
    {
        y=to[i];
        if (vis[y]) continue;
        dfs(y);
        son[x]+=son[y];
    }
    maxl+=min(son[x],2*k-son[x]);//需要“流向”该点父亲的边的数量
}
int main() {
    scanf("%d%d",&n,&k);
    for (int i=0;i<2*k;++i)
    {
        scanf("%d",&x);
        son[x]=1;
    }
    for (int i=0;i<n-1;++i)
    {
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(1);
    printf("%d",maxl);
    return 0;
}