AcWing 351. 树网的核

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 351. 树网的核原题链接困难

作者：

Fighting_Peter , 2020-09-12 11:23:26 , 所有人可见 , 阅读 511

题目描述

设T=(V, E, W) 是一个无圈且连通的无向图（也称为无根树），每条边带有正整数的权，我们称T为树网（treenetwork），其中V, E分别表示结点与边的集合，W表示各边长度的集合，并设T有n个结点。

路径：树网中任何两结点a,b都存在唯一的一条简单路径，用d(a,b)表示以a,b为端点的路径的长度，它是该路径上各边长度之和。

我们称d(a,b)为a,b两结点间的距离。

一点v到一条路径P的距离为该点与P上的最近的结点的距离：

d(v，P)=min{d(v，u)，u为路径P上的结点}。

树网的直径：树网中最长的路径称为树网的直径。

对于给定的树网T，直径不一定是唯一的，但可以证明：各直径的中点（不一定恰好是某个结点，可能在某条边的内部）是唯一的，我们称该点为树网的中心。

偏心距ECC(F)：树网T中距路径F最远的结点到路径F的距离，即：

ECC(F)=max{d(v,F),v∈V}

任务：对于给定的树网T=(V, E,W)和非负整数s，求一个路径F，它是某直径上的一段路径（该路径两端均为树网中的结点），其长度不超过s（可以等于s），使偏心距ECC(F)最小。

我们称这个路径为树网T=(V,E,W)的核（Core）。

必要时，F可以退化为某个结点。

一般来说，在上述定义下，核不一定只有一个，但最小偏心距是唯一的。

输入格式

包含n行：第1行，两个正整数n和s，中间用一个空格隔开，其中n为树网结点的个数，s为树网的核的长度的上界，设结点编号依次为1, 2, …, n。

从第2行到第n行，每行给出3个用空格隔开的正整数，依次表示每一条边的两个端点编号和长度。

例如，“2 4 7”表示连接结点2与4的边的长度为7。

所给的数据都是正确的，不必检验。

输出格式

只有一个非负整数，为指定意义下的最小偏心距。

数据范围

$n≤500000,s<2^{31}$

题目分析

首先找直径，由于需要记录直径上所有点并记下路径，推荐采用两次$bfs$或$dfs$，这里采用两次$dfs$（代码少）

然后如何求偏心距？
首先考虑不在直径上的点，假设不在直径上点距路径最远的节点$u$，那么即路径上的存在一个点$v$不经过直径上的点能够到达的最远点是$u$。因此先不考虑直径上的点对偏心距的贡献，尝试预处理从路径上的点不经过直径上的点能到达的最远距离$O(n)$，而直径上的点肯定是直径端点到路径端点才可能对偏心距有贡献。而整条路径的偏心距就是上述所求取$max$

整理一下就是在直径上选一条路径$S$，不妨设$S$的端点为$l$和$r$，而偏心距就是路径上的每个点不经过直径能够到达的最远点以及直径端点到路径端点取个$max$，如果我们枚举$l$和$r$（只需满足$|dist_r-dist_r| \leq s$）即可得出答案$O(n^2)$。
求路径上的每个点不经过直径能够到达的最远点是典型的滑动窗口求最值采用单调队列优化$O(n)$。优化后我们只需要枚举$r$即可。对于$l$贪心路径上的点越多越好，因此$l$双指针可以维护出来$O(n)$，那么直径端点到路径端点也就即可求出来。

代码——$O(n)$

// O(n)
#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
const int N=500010;
int h[N],e[N*2],ne[N*2],w[N*2],idx;
void add(int a,int b,int c)
{
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
int n,s;
int top,dnow;
int dist[N],fa[N];
void dfs1(int u)
{
    if(dist[u]>dnow)
    {
        dnow=dist[u];
        top=u;
    }
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==fa[u]) continue;
        fa[j]=u;
        dist[j]=dist[u]+w[i];
        dfs1(j);
    }
}
int q[N],tt=-1,hh=0;
int dmx[N];
bool st[N];
int dfs2(int u,int f)
{
    int d=0;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(j==f||st[j]) continue;
        d=max(d,w[i]+dfs2(j,u));
    }
    return d;
}
int main()
{
    cin>>n>>s;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }
    dfs1(1);
    dist[top]=0;
    int ed=top;
    fa[top]=0;
    dnow=0;
    dfs1(top);
    int start=top;
    for(int i=top;i;i=fa[i]) st[i]=1;

    for(int i=1;i<=n;i++)
         if(st[i]) dmx[i]=dfs2(i,0);
    int res=0x3f3f3f3f;
    int l=top;
    for(int i=top;i;i=fa[i])
    {
        while(tt>=hh&&dist[q[hh]]-dist[i]>s) hh++;
        while(dist[l]-dist[i]>s) l=fa[l];
        while(tt>=hh&&dmx[i]>=dmx[q[tt]]) tt--;
        q[++tt]=i;
        int now=max(max(dist[start]-dist[l],dist[q[tt]]-dist[ed]),dmx[q[hh]]);
        res=min(res,now);
    }
    cout<<res<<endl;
    return 0;
}