M_sea

CF835F Roads in the Kingdom
CodeForcesLuogu分析直接考虑删哪条似乎很不可做的样子,我们考虑枚举删掉哪条然后快速算直径。把环拉出来...
扫描右侧二维码阅读全文
16
2019/04

CF835F Roads in the Kingdom

CodeForces

Luogu

分析

直接考虑删哪条似乎很不可做的样子,我们考虑枚举删掉哪条然后快速算直径。

把环拉出来,这样子每个环上的点就对应了一颗子树。

显然我们只能删掉环上的边。这里为了表述方便,把环上的点顺时针重编号为 $1\sim sz$ 。

假设当前删掉了 $(x-1,x)$ 。设 $f[i]$ 表示 $i$ 的子树中的节点到 $i$ 的最长路径长度, $sum[i]$ 表示 $i$ 逆时针走到 $x$ 的距离。那么一条路径可以表示为 $f[i]-sum[i]+f[j]+sum[j]$ 。

那么只要 $f[i]-sum[i]$ 和 $f[j]+sum[j]$ 分别最大即可。只要用两个 $\mathrm{set}$ 维护就行了。

然后可能会有选出的 $i=j$ 的情况,此时取一个 $\mathrm{set}$ 中的最大值和另一个 $\mathrm{set}$ 中的次大值即可。

否则可以证明 $i$ 一定在 $j$ 的前面。

考虑一下 $x$ 加 $1$ 变为 $y$ 时发生了什么。

首先所有的 $sum$ 值都要变化,但是答案式子中 $sum$ 相当于作差,所以实际上可以不变。(当然实际值比存的 $sum$ 值小了 $sum[y]$ )。

然后还要把 $sum[x]$ 重新丢到后面去。因为存的 $sum$ 值比实际值大了 $sum[y]$ ,所以要把 $sum[x]$ 加上环长接在最后面(画图可知)。

然后这题就做完了。最后的答案要和所有子树的直径取个 $\max$ 。

如果以上内容有不理解的建议自己画图。另外有问题欢迎找我。

代码细节非常多,详见代码。

代码

// =================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// =================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#define re register
#define mp make_pair
#define IT multiset<pair<int,int>,greater<pair<int,int> > >::iterator
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=400000+10;

int n;
struct Edge { int v,w,nxt; } e[N<<1];
int head[N];

inline void addEdge(int u,int v,int w) {
    static int cnt=0;
    e[++cnt]=(Edge){v,w,head[u]},head[u]=cnt;
}

int eid[N],in[N],fa[N];
int dfn[N],tim=0,top=0;
pair<int,int> cir[N];
int f[N],mx;
int sum[N];
set<pair<int,int>,greater<pair<int,int> > > s1,s2;

inline void find_circle(int u) {
    dfn[u]=++tim;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa[u]) continue;
        if (dfn[v]) {
            if (dfn[v]<dfn[u]) continue;
            for (re int i=v;i!=u;i=fa[i])
                cir[++top]=mp(i,e[eid[i]].w),in[i]=1;
            cir[++top]=mp(u,e[i].w),in[u]=1;
            return;
        }
        fa[v]=u,eid[v]=i; find_circle(v);
        if (top) return;
    }
}

inline void dfs(int u,int fa) {
    f[u]=0; int mx1=0,mx2=0;
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v,w=e[i].w;; if (v==fa||in[v]) continue;
        dfs(v,u); f[u]=max(f[u],f[v]+w);
        if (f[v]+w>mx1) mx2=mx1,mx1=f[v]+w;
        else if (f[v]+w>mx2) mx2=f[v]+w;
    }
    mx=max(mx,mx1+mx2);
}

signed main() {
    n=read();
    for (re int i=1;i<=n;++i) {
        int u=read(),v=read(),w=read();
        addEdge(u,v,w),addEdge(v,u,w);
    }
    find_circle(1);
    for (re int i=1;i<=top;++i)
        cir[i+top]=cir[i],dfs(cir[i].first,0);
    for (re int i=2;i<=top*2;++i) sum[i]=sum[i-1]+cir[i-1].second;
    for (re int i=1;i<=top;++i) {
        s1.insert(mp(f[cir[i].first]+sum[i],i));
        s2.insert(mp(f[cir[i].first]-sum[i],i));
    }
    int ans=1e18;
    for (re int i=1;i<=top;++i) {
        int now;
        if (s1.begin()->second==s2.begin()->second) {
            IT it=s1.begin(); ++it;
            now=it->first+s2.begin()->first;
            it=s2.begin(); ++it;
            now=max(now,it->first+s1.begin()->first);
        }
        else now=s1.begin()->first+s2.begin()->first;
        ans=min(ans,now);
        s1.erase(mp(f[cir[i].first]+sum[i],i));
        s2.erase(mp(f[cir[i].first]-sum[i],i));
        s1.insert(mp(f[cir[i+top].first]+sum[i+top],i+top));
        s2.insert(mp(f[cir[i+top].first]-sum[i+top],i+top));
    }
    printf("%lld\n",max(ans,mx));
    return 0;
}
最后修改:2019 年 07 月 13 日 02 : 43 PM

发表评论