牛客网 meeting 【树的直径】

A new city has just been built. There're 牛客网 meeting  【树的直径】 interesting places numbered by positive numbers from 牛客网 meeting  【树的直径】 to 牛客网 meeting  【树的直径】.

In order to save resources, only exactly 牛客网 meeting  【树的直径】 roads are built to connect these 牛客网 meeting  【树的直径】 interesting places. Each road connects two places and it takes 1 second to travel between the endpoints of any road.

There is one person in each of the places numbered 牛客网 meeting  【树的直径】 and they've decided to meet at one place to have a meal. They wonder what's the minimal time needed for them to meet in such a place. (The time required is the maximum time for each person to get to that place.)

题意:给你一个n个节点n-1条边的树,其中k个人在某些节点上,他们希望到同一个地方的时间最小(时间是最后一个人到的时间)。

思路:其实很简单,只需要求出来包含这么多节点的最小树的直径向上取整就行了,当时一直往重心上想。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
vector<int> e[maxn];
map<int, int> mp;
int cnt, ans;
int l, k;
 
void dfs(int u, int fa, int len)
{
    if(cnt > k)
        return;
    if(mp[u])
    {
        ++cnt;
        if(len > ans)
        {
            ans = len;
            l = u;
        }
    }
    for(int i = 0; i < e[u].size(); ++i)
    {
        int v = e[u][i];
        if(v == fa)
            continue;
        dfs(v, u, len + 1);
    }
}
 
int main()
{
    int n;
    scanf("%d%d", &n, &k);
    for(int i = 1; i < n; ++i)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].push_back(v);
        e[v].push_back(u);
    }
    int tmp;
    for(int i = 1; i <= k; ++i)
    {
        int u;
        scanf("%d", &u);
        mp[u] = 1;
        tmp = u;
    }
    cnt = ans = 0;
    dfs(tmp, 0, 0);
    cnt = 0;
    dfs(l, 0, 0);
    printf("%d\n", (ans + 1)/2);
    return 0;
}

 

上一篇:ISE post-place&route仿真准备


下一篇:八皇后位运算优化