NOIP2007提高组.树网的核

题目

351. 树网的核

算法标签: 树的直径, 贪心, 二分, 单调队列

思路

树的直径的中点是唯一的, 树中的两个直径是有交集的, 因此树的直径的交点是唯一的

可以证明, 无论对于树的任意一个直径, 求的最小的核一定是相同的, 只会相交一段, 最多退化成一个点

两个颜色分别代表两条直径(代表的是路径不是边), 可以证明任意两条直径必然相交并且相交于一个中心

核可以从任意一天一条路径上取, 但是不知道那个偏心距最小, 因此需要枚举所有的核, 但是这样时间复杂度就太高了, 但是我们可以猜想无论从任意一条直径上取, 得到的最小偏心距是一样的

如果核心都是再公共部分, 那么就能证明所有直径的最小偏心距是一样的, 因此只需要证明删除蓝色位置不影响答案]

对于上述两条直径$a+b+x=c+d+x=s$, 最小偏心距一定$\ge c$, 因为对于蓝色段来说影响的点只有$a$分支, 可以将$a$分支上的点分为两类, 一个是在分支上的, 一个是不在分支上的

对于从蓝色路径上的分支, 一定有$s1<s2+s3$, 因为$s2,s3$在树的直径上, 因为偏心距是最短距离的最大值, 因为一定$<c$因此不会对答案造成影响

同理如果对于蓝色路径外的点, 也有$s1<s2$, 因为$s2+s3=c$, 因此也不需要考虑

最后将问题转化为在一条直径上找长度不超过$s$的一段, 使得其他点到这个线段的长度的最大值最小, 因为求最大值最小可以考虑进行二分, 长度越长包含的点越多, 最小值不会变差, 直接取最长的$s$, 相当于在滑动窗口求极值, 可以使用单调队列求解

在求的过程中也可以分类讨论, 对于挂在核上的点, 可以预处理每个点到直径的距离, 记录外面点的最大值, 这样就能滑动窗口求最值, 对于挂在核以外的点,

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>

#define x first
#define y second

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;
const int N = 500010, M = N << 1;

int n, m;
int head[N], ed[M], ne[M], w[M], idx;
int dist[N], pre[N];
vector<PII> path;
bool st[N];

void add(int u, int v, int val) {
   
    ed[idx] = v, ne[idx] = head[u], w[idx] = val, head[u] = idx++;
}

// 使用BFS计算距离
void bfs(int start) {
   
    memset(dist, 0x3f, sizeof dist);
    memset(pre, -1, sizeof pre);
    int q[N], h = 0, t = -1;
    q[++t] = start;
    dist[start] = 0;

    while (h <= t) {
   
        int u = q[h++];
        for (int i = head[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            if (dist[v] > dist[u] + w[i]) {
   
                dist[v] = dist[u] + w[i];
                pre[v] = u;
                q[++t] = v;
            }
        }
    }
}

// 获取距离最大的节点
int get_max() {
   
    int t = 1;
    for (int i = 1; i <= n; i++) if (dist[t] < dist[i]) t = i;
    return t;
}

// 计算最大距离
int calc_max_dist(int start) {
   
    int res = 0;
    int q[N], h = 0, t = -1;
    q[++t] = start;
    dist[start] = 0;

    while (h <= t) {
   
        int u = q[h++];
        res = max(res, dist[u]);

        for (int i = head[u]; ~i; i = ne[i]) {
   
            int v = ed[i];
            if (!st[v]) {
   
                st[v] = true;
                dist[v] = dist[u] + w[i];
                q[++t] = v;
            }
        }
    }
    return res;
}

bool check(int mid) {
   
    int u = 0, v = path.size() - 1;
    while (u + 1 < path.size() && path[u + 1].y <= mid) u++;
    while (v - 1 >= 0 && path.back().y - path[v - 1].y <= mid) v--;
    if (u > v) return true;
    if (path[v].y - path[u].y > m) return false;

    memset(st, false, sizeof st);
    memset(dist, 0, sizeof dist);
    for (auto &p : path) st[p.x] = true;

    for (int i = u; i <= v; ++i) {
   
        if (calc_max_dist(path[i].x) > mid) return false;
    }

    return true;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);
    cin >> n >> m;

    for (int i = 0; i < n - 1; ++i) {
   
        int u, v, w;
        cin >> u >> v >> w;
        add(u, v, w), add(v, u, w);
    }

    // 第一次BFS找直径端点u
    bfs(1);
    int u = get_max();

    // 第二次BFS找直径端点v并记录路径
    bfs(u);
    int v = get_max();

    // 回溯记录直径路径
    while (v != -1) {
   
        path.push_back({
   v, dist[v]});
        v = pre[v];
    }
    reverse(path.begin(), path.end());

    // 二分查找最小偏心距
    int l = 0, r = 2e9;
    while (l < r) {
   
        int mid = (LL)l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    cout << l << "\n";
    return 0;
}