题解：P3596 [POI 2015 R3] 高速公路现代化 Highway modernization

· · 题解

题解：P3596 [POI 2015 R3] 高速公路现代化 Highway modernization

前言

无需 dp，直接无脑 DS 再加上卡常就行。喜提最劣解。

分析

首先拆分问题，假若给你两颗树，让你求出这两个树相连的能构成的最长直径，和最短直径，并给出构造方案。

最长直径应该比较显然，就是把两颗树的直径的端点相连就行了。

最短直径的话，显然 \max{\text{diameter}_a,\text{diameter}_b} 会有贡献。然后还会有通过连接点的贡献。所以，我们现在的目标是让通过连接点的最长路径更短。

那么再细分以下，我们称过连接点的最长路径的为跨越路径。思考两颗树分别对跨越路径的贡献，显然是 \leq \text{diameter} 的。那每颗树最小能作出多小的贡献？考虑将树的中心作为根，其最深叶子节点的深度的 \max 是最小的。为 \lceil\frac{\text{diameter}}{2}\rceil。

所以跨越路径的下界就是 \lceil\frac{\text{diameter}_a}{2}\rceil+\lceil\frac{\text{diameter}_b}{2}\rceil+1。

构造就是将两颗树的中心相连。

由此我们就完成了第一步的推断过程。

实现

那么考虑枚举断哪条边，现在要做的就是快速算出子树内的直径和子树补内的直径和端点信息。

注意到一个子树补有良好的性质在于他的 \operatorname{dfn} 序是两个区间的并。并且直径也有良好的性质是结合律。

经验：\ 求某一个集合的直径有两种方法，分别是 \operatorname{dfn} 序和欧拉序上建线段树。\ 其中 \operatorname{dfn} 序可以帮你维护出该直径的端点信息，但是要求集合中的点集是连续的。\ 欧拉序则是维护一个 dep_x+dep_y-2\times dep_{\operatorname{lca}(x,y)} 这个类型的东西（x\leq y）。不要求连续点集。并且支持边权修改。

在本题，我选择的是 \operatorname{dfn} 序求直径。

然后注意到我们还要求中心，这个可以写个倍增，从直径较深的端点跳 \lceil\frac{diameter}{2}\rceil 次就行。

分析一波复杂度是超大常数 O(N\log^2N)（本人在线段树的 push_up 中求 \operatorname{lca} 未使用 O(1) 复杂度）。

优化

你注意到这个写法是不需要大脑，但是常数过大，我加了卡常才通过。

回到原问题。没有修改操作，线段树没有很大必要。注意到子树补其实是 \operatorname{dfn} 序的一段连续前缀并上连续后缀。那么你预处理出前缀和后缀的直径信息就行。子树答案的求解你可以写一个 dp 就行了。

求树的中心使用倍增也是没有必要的。注意到，我们只需要在最后求出最优的直径后再算即可，暴力跳都没问题。

那么复杂度为超小常数 O(N\log N) 瓶颈在于求 \operatorname{lca}。

代码

申明：本人写的是优化思路之前的代码，优化思路若读者看懂了可以自行尝试。应该比优化前的要短不少，且常数优秀。

#include <bits/stdc++.h>
#define vi vector<int>
#define pb emplace_back
using namespace std;
namespace OIfast{
    char buf[1<<21],*p1,*p2,*top, buffer[1<<21];
    #define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?0:*p1++)
    #define ri register
template<typename T>
    inline void rd(T& x)
    {
        x=0;
        ri short f=1;
        ri char c=gc();
        while(c<'0' || c>'9'){if(c=='-')f=-1;c=gc();}
        while(c>='0' && c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc();
        x*=f;
    }
template<typename T,typename ...Args>
    inline void rd(T& x,Args& ...args)
    {
        rd(x),rd(args...);
    }
template<typename T>
    inline void prt(ri T n)
    {
        ri short sta[20];
        ri short top=0;
        if(n<0)n=~n+1,putchar('-');
        do{
            sta[top++]=n%10;
            n/=10;
        }while(n);
        while(top)putchar(sta[--top]^48);
        return ;
    }
template<typename T>
    inline void wr(ri T n,ri char c)
    {   
        prt(n),putchar(c);
        return ;
    }
    #undef gc
    #undef ri
}using namespace OIfast;
constexpr int N=5e5+5,inf=1e9;
int n;
vi e[N];
int dep[N],dfn[N],id[N],sz[N];
template<typename T>
inline T maxx(T x,T y){return x<y?y:x;}
template<typename T>
inline T minn(T x,T y){return x<y?x:y;}
namespace tree_cut
{
int idx;
int top[N],fa[N],son[N];
int st[N][20];
void dfs(int u=1,int fa=0)
{
    tree_cut::fa[u]=fa;
    st[u][0]=fa;
    dep[u]=dep[fa]+1;
    for(int i=1;(1<<i)<=dep[u];i++)st[u][i]=st[st[u][i-1]][i-1];
    sz[u]=1;
    id[dfn[u]=++idx]=u;
    for(auto v:e[u])
    {
        if(v==fa)continue;
        dfs(v,u);
        sz[u]+=sz[v];
        if(sz[v]>sz[son[u]])son[u]=v;
    }
}
void dfs1(int u=1,int top=1)
{
    tree_cut::top[u]=top;
    if(son[u])dfs1(son[u],top);
    for(auto v:e[u])
    {
        if(v==fa[u] || v==son[u])continue;
        dfs1(v,v);
    }
}
void init(){dfs(),dfs1();}
int lca(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]<dep[top[v]])swap(u,v);
        u=fa[top[u]];
    }
    return dep[u]<dep[v]?u:v;
}
int calc(int u,int v){return (u!=-1 && v!=-1)?dep[u]+dep[v]-2*dep[lca(u,v)]:-inf;}
int get(int u,int k)
{
    for(int i=19;~i;i--)if(k>=(1<<i))k-=(1<<i),u=st[u][i];
    return u;
}
}
using tree_cut::calc;
using tree_cut::get;
struct node{
    int len,x,y;
    node()=default;
    node(int len,int x,int y):len(len),x(x),y(y){}
    inline bool operator<(const node& oth){return len<oth.len;}
    inline node operator+(const node& oth)
    {
        if(!~len)return oth;
        if(!~oth.len)return *this;
        node res=maxx(*this,oth);
        res=maxx(res,node(calc(x,oth.x),x,oth.x));
        res=maxx(res,node(calc(x,oth.y),x,oth.y));
        res=maxx(res,node(calc(y,oth.x),y,oth.x));
        res=maxx(res,node(calc(y,oth.y),y,oth.y));
        if(dep[res.x]<dep[res.y])swap(res.x,res.y);
        return res;
    }
}tr[N<<2];
#define ls k<<1
#define rs k<<1|1
inline void pu(int k){tr[k]=tr[ls]+tr[rs];}
void build(int k,int l,int r)
{
    if(l==r)return void(tr[k]=node(0,id[l],id[l]));
    int mid=l+r>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pu(k);
}
node ask(int k,int l,int r,int L,int R)
{
    if(r<L || R<l)return node(-1,-1,-1);
    if(L<=l && r<=R)return tr[k];
    int mid=l+r>>1;
    return ask(ls,l,mid,L,R)+ask(rs,mid+1,r,L,R);
}
struct ans{
    int len,a,b,c,d;
    ans()=default;
    ans(int len,int a,int b,int c,int d):len(len),a(a),b(b),c(c),d(d){}
    inline bool operator<(const ans& oth)const{return len<oth.len;}
    void out(){cout<<len+1<<' '<<a<<' '<<b<<' '<<c<<' '<<d<<'\n';}
}mx,mn;
void dfs(int u=1,int fa=0)
{
    if(fa)
    {
        node le=ask(1,1,n,1,dfn[u]-1),ri=ask(1,1,n,dfn[u]+sz[u],n);
        le=le+ri;
        node now=ask(1,1,n,dfn[u],dfn[u]+sz[u]-1);
        ans nmx=ans(le.len+now.len,u,fa,le.x,now.x);
        mx=maxx(mx,nmx);
        ans nmn=ans(max({(le.len+1)/2+(now.len+1)/2,le.len-1,now.len-1}),u,fa,get(le.x,le.len+1>>1),get(now.x,now.len+1>>1));
        mn=minn(mn,nmn);
    }
    for(auto v:e[u])
    {
        if(v==fa)continue;
        dfs(v,u);
    }
}
#undef ls
#undef rs
int main()
{
#ifndef ONLINE_JUDGE
    freopen("data.in","r",stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    rd(n);
    for(int i=1,u,v;i<n;i++)
        rd(u,v),e[u].pb(v),e[v].pb(u);
    tree_cut::init();
    build(1,1,n);
    mx.len=0,mn.len=inf;
    dfs();
    mn.out(),mx.out();
    return 0;
}

点个赞再走吧！