题意

给定一棵边带权的树,在直径上取一条长度小于等于 s 的路径(可以退化成点)最小化树上其他点到路径上的最大距离。

思路

观察直径的性质

首先一棵树可以有很多条直径,但是他们分别必定关于他们的交点对称

所以我们可以只考虑一条直径,不妨设两个端点分别为 P_1P_2下面指的路径全部为直径上的路径

然后,对于一个路径上的一个点来说,距离其最远的点一定在直径的某一个端点上(反证法:如果不是最远的话那直径就不是直径了),很明显,如果路径是这样的:P_1-A_1-A_2-P_2,则直径的端点对答案产生的贡献即为 \max(dis(P_1,A_1),dis(A_2,P_2)

首先 dfs 两遍求出 P_1P_2,然后预处理出直径上的点分别到两端点的距离并将所有直径上的点打入一个 vector,复杂度为 O(n)

其他的贡献

不妨考虑一个极端情况:s=dis(P_1,P_2),这样的话直径两个端点对答案产生的贡献就为 0,然而答案并不一定是这样的:其他不在直径上的点也会产生贡献。所以对于直径上的某个点,一定要处理出与其相连的非直径边能到达的最远距离,dfs 一遍也可做到。

dp

最后就是 dp 了,在直径上可以尺取法,一路考虑下第二种贡献和直径端点产生的贡献,答案取 min 即可。

时间复杂度 O(n),可以通过 NOIP 原题

#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>

using std::vector;

const int maxn=500000+5;

inline int read()
{
    char c = getchar();
    int s = 0;
    while (!isdigit(c))
        c = getchar();
    while (isdigit(c))
        s = 10 * s + c - '0', c = getchar();
    return s;
}

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}

int n,s;

struct edge
{
    int from,to,w,nxt;
}e[maxn<<1];

int head[maxn],cntedge;

inline void add(int u,int v,int w)
{
    e[++cntedge].to=v;
    e[cntedge].w=w;
    e[cntedge].from=u;
    e[cntedge].nxt=head[u];
    head[u]=cntedge;
    return;
}

int dis[maxn];
int disp1[maxn],disp2[maxn];
int p1,p2;//直径的两个端点
bool vis[maxn];
vector<int> diam;

void dfs1(int u,int fa)
{
    for(int i=head[u];i;i=e[i].nxt)
    {
        int &v=e[i].to;
        if(v==fa)
            continue;
        dis[v]=dis[u]+e[i].w;
        dfs1(v,u);
    }
    return;
}

bool find_diameter(int u,int fa)
{
    if(u==p2)
        return true;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int &v=e[i].to;
        if(v==fa)continue;
        disp1[v]=disp1[u]+e[i].w;
        if(find_diameter(v,u))
        {
            diam.push_back(v);
            return true;
        }
    }
    return false;
}

int dfs2(int u)
{
    vis[u]=1;
    int tmp=0;
    for(int i=head[u];i;i=e[i].nxt)
    {
        int v=e[i].to;
        if(vis[v])continue;
        dis[v]=dis[u]+e[i].w;
        dfs2(v);
        tmp=max(tmp,dis[v]);
    }
    return tmp;
}

int main()
{
    n=read(),s=read();
    for(int i=1;i<n;++i)
    {
        int u=read(),v=read(),w=read();
        add(u,v,w);
        add(v,u,w);
    }
    dfs1(1,0);
    for(int i=1,maxdist=0;i<=n;dis[i++]=0)
        if(dis[i]>maxdist)
            maxdist=dis[i],p1=i;
    dfs1(p1,0);
    for(int i=1,maxdist=0;i<=n;dis[i++]=0)
        if(dis[i]>maxdist)
            maxdist=dis[i],p2=i;
    find_diameter(p1,0);
    diam.push_back(p1);
    for(int i:diam)
        vis[i]=true;
    for(int i=1;i<=n;++i)
        disp2[i]=disp1[p2]-disp1[i];
    for(int i=1;i<=n;++i)
        dis[i]=dfs2(i);
    int ans=0x3f3f3f3f;
    for(int i=0;i<diam.size();++i)
    {
        int tmp=0;
        for(int j=i;j<diam.size();++j)
        {
            if(disp1[diam[i]]-disp1[diam[j]]>s)break;
            tmp=max(tmp,dis[diam[j]]);
            int tmp1=max(tmp,max(disp1[diam[j]],disp2[diam[i]]));
            ans=min(ans,tmp1);
        }
    }
    printf("%d\n",ans);
    return 0;
}
最后修改日期:2020年12月1日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。