[NOIP2007 提高组] 树网的核

[SDOI2011]消防(这一道是上一道的数据加强版)

题意:给定一棵树,找出一条长度小于s的路径,使得该树上的结点到这条路径的最大值最小

首先根据树的直径的定义,对于任意一条路径,距离其最远的点一定在树的直径的端点上.

为了方便求得答案,不妨假设路径就在树的直径上,只需要求出一条路径在树的直径内使得端点到该路径的距离最小

但是有一些特殊情况,比如路径的端点就是树的直径的端点,所以我们还需要求出树上其他点非直径的点到树的直径上的点的最大距离

代码实现,直接用两边dfs求出树的直径,然后维护一下树的直径的前缀和,在树的直径上维护一个单调队列,每次更新答案

代码

#include<iostream>
#include<cstdio>
using namespace std;
const int N = 3e5 + 5;

int cnt, d[N], dis[N], sum[N], q1[N], q2[N];
int f1[N], f2[N], len, p1[N], p2[N], root, dim[N];
int head[N], ver[2 * N], net[2 * N], edge[2 * N], idx;
bool is[N];

void add(int a, int b, int c)
{
    net[++idx] = head[a], ver[idx] = b, edge[idx] = c, head[a] = idx;
}

void dfs1(int u, int fa)
{
    for (int i = head[u]; i; i = net[i])
    {
        int v = ver[i];
        if (v == fa)
            continue;
        dfs1(v, u);
        d[v] = edge[i];
        if (f1[u] < f1[v] + edge[i])
        {
            p2[u] = p1[u], p1[u] = v;
            f2[u] = f1[u], f1[u] = f1[v] + edge[i];
        }
        else if (f2[u] < f1[v] + edge[i])
            f2[u] = f1[v] + edge[i], p2[u] = v;
        if (f1[u] + f2[u] > len)
            root = u, len = f1[u] + f2[u];
    }
}

void dfs2(int u)
{
    if (p1[u])
        dfs2(p1[u]);
    sum[u] = sum[p1[u]] + d[p1[u]];
    dim[++cnt] = u, is[u] = true;
    if (u == root)
    {
        p1[u] = p2[u];
        while (p1[u])
        {
            dim[++cnt] = p1[u], is[p1[u]] = true;
            sum[p1[u]] = sum[u] + d[p1[u]], u = p1[u];
        }
        return;
    }
}

void dfs3(int u, int fa)
{
    for (int i = head[u]; i; i = net[i])
    {
        int v = ver[i];
        if (v == fa || is[v])
            continue;
        dfs3(v, u);
        dis[u] = max(dis[u], dis[v] + edge[i]);
    }
}

int main()
{
    int n, s;
    scanf("%d%d", &n, &s);
    for (int i = 1; i < n; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        add(u, v, w), add(v, u, w);
    }
    dfs1(1, 0);
    dfs2(root);
    for (int i = 1; i <= cnt; i++)
        dfs3(dim[i], 0);
    int f1 = 0, t1 = -1, f2 = 0, t2 = -1, ans = 0x3f3f3f3f;
    for (int i = 1; i <= cnt; i++)
    {
        int x = dim[i];
        while (f1 <= t1 && sum[x] - sum[q1[f1]] > s) f1++;
        while (f2 <= t2 && sum[x] - sum[q2[f2]] > s) f2++;
        while (f2 <= t2 && dis[x] > dis[q2[t2]]) t2--;
        q1[++t1] = q2[++t2] = x;
        int d1 = sum[q1[f1]], d2 = sum[dim[cnt]] - sum[q1[t1]];
        ans = min(ans, max(dis[q2[f2]], max(d1, d2)));
    }
    printf("%d", ans);
    return 0;
}