题目大意

有一棵基环树,现在你需要从基环树上选择一条边被删除,满足:
1. 删除后形成的是一棵树(不是森林)
2. 删除后的直径尽量小

并且求出最小可能的直径

题解

首先基环树求直径大家都会。。。Island 岛屿(虽然由于我太菜至今还没卡常成功)
然后这个题我们考虑如何删除一条边之后快速算出直径。
我们只考虑最长路径跨过环的情况(不跨过环的可以轻松处理)
对于每个子树做直径 dp 是必须的,然后我们考虑如何快速换边。。
首先我们考虑我们暴力如果枚举每一对有序对 $(x,y)$ 并且默认删除了 x 逆时针方向的第一条边的话,这种暴力能遍取每一种可能的情况的。
那我们就考虑现在做到了点 $x$ (也就是删除了它逆时针方向的第一条边),令 $dis_v$ 表示 $v$ 到 $x$ 的距离,$val_v$ 表示 $v$ 的子树的最长且一端在该点上的链。那么我们分别用 $set$ 维护处 $val_v+dep_v$ 和 $val_v-dep_v$ 就可以了。
现在考虑如果 $x$ 变换为顺时针方向上的第一个点 $y$ ,会造成什么影响。
我们设环长为 $sm$,那么显然每次操作只会影响到 $dis$,我们设边 $(x,y)$ 的权值为 $w$,发现 $dis_x = dis_x + sm - w, dis_y = dis_y - w(\forall y \neq x)$(即使是赋值操作也写成加法统一比较好)
相当于单点加和全体减了,由于查询的时候是对 $dis$ 做差,所以我们可以无视第二个操作。
然后就码码码就行了。
这个题貌似和 BZOJ3242 撞了,双倍经验。。。

/*
 * Author: RainAir
 * Time: 2019-08-30 19:33:54
 */
#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <assert.h>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>

#define fi first
#define se second
#define U unsigned
#define P std::pair<LL,LL>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
#define int LL
const int MAXN = 2e5 + 5;

struct Edge{
    int to,w,nxt;
}e[MAXN<<1];

int head[MAXN],n,m,cnt,du[MAXN];
std::unordered_map<LL,int> S;

inline void add(int u,int v,int w){
    if(u > v) std::swap(u,v);
    if(!S[1ll*u*n+v]) S[1ll*u*n+v] = w;
    else S[1ll*u*n+v] = std::min(S[1ll*u*n+v],w);
    du[u]++;du[v]++;
    e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,w,head[v]};head[v] = cnt;
}

inline int calc(int u,int v){
    if(u > v) std::swap(u,v);
    return S[u*n+v];
}

bool circled[MAXN];
std::vector<int> circle;

inline void topsort(){
    std::queue<int> q;
    FOR(i,1,n) if(!du[i]) q.push(i);
    while(!q.empty()){
        int v = q.front();q.pop();circled[v] = false;
        for(int i = head[v];i;i = e[i].nxt){
            if(!--du[e[i].to]) q.push(e[i].to);
        }
    }
    FOR(i,1,n) if(circled[i]) m++;
}

int f[MAXN][2],ans = LLONG_MAX,len = 0;
int dis[MAXN],val[MAXN];

inline void dp(int v,int fa=0){
    for(int i = head[v];i;i = e[i].nxt){
        if(e[i].to == fa || circled[e[i].to]) continue;
        dp(e[i].to,v);int gx = f[e[i].to][0]+e[i].w;
        if(gx > f[v][0])
            f[v][1] = f[v][0],
            f[v][0] = gx;
        else if(gx > f[v][1]) f[v][1] = gx;
    }
    len = std::max(len,f[v][1]+f[v][0]);
}

int sm = 0;
std::set<P> s1,s2;
// s1:val-dis s2: val+dis

inline void Solve(){
    if(m == 2){ // force
        ans = val[1]+val[2]+calc(circle[0],circle[1]);
        return;
    }
    FOR(i,1,m) s1.insert(MP(val[i]-dis[i],i)),s2.insert(MP(val[i]+dis[i],i));
    FOR(i,1,m){
        auto x = --s1.end(),y = --s2.end();
        if(x->se == y->se){
            int gx1 = (--x)->fi+y->fi;++x;
            int gx2 = x->fi+(--y)->fi;++y;
            ans = std::min(ans,std::max(gx1,gx2)); // FIX
        }
        else ans = std::min(ans,x->fi+y->fi);
        s1.erase(MP(val[i]-dis[i],i));
        s2.erase(MP(val[i]+dis[i],i));
        s1.insert(MP(val[i]-dis[i]-sm,i));
        s2.insert(MP(val[i]+dis[i]+sm,i));
    }
}

bool vis[MAXN];

inline void getcircle(){
    if(m == 2){ // force
        FOR(i,1,n) if(circled[i]) circle.pb(i);
        return;
    }
    FOR(i,1,n) if(!circled[i]) vis[i] = true; // bord
    int v,t;
    ROF(i,n,1) if(circled[i]) v = i;
    t = v;//vis[v] = true;
    int pre = -1;
    do{
        circle.pb(t);
        for(int i = head[t];i;i = e[i].nxt){
            if(e[i].to == pre) continue;
            if(!vis[e[i].to]){
                vis[e[i].to] = true;
                pre = t;
                t = e[i].to;
                break;
            }
        }
    }while(t != v);
}

signed main(){
 //   freopen("a.in","r",stdin);
    scanf("%lld",&n);
    std::fill(circled+1,circled+n+1,true);
    std::fill(du+1,du+n+1,-1);
    FOR(i,1,n){
        int u,v,w;scanf("%lld%lld%lld",&u,&v,&w);
        add(u,v,w);
    }
    topsort();getcircle();
    assert(m == (int)circle.size());
    FOR(i,0,m-1){
        dp(circle[i]);val[i+1] = f[circle[i]][0];
        if(i > 0) dis[i+1] = calc(circle[i-1],circle[i]),sm += dis[i+1];
    }
    //dis[m] = calc(circle[0],circle[m-1]);
    sm += calc(circle[0],circle[m-1]);
    FOR(i,1,m) dis[i] += dis[i-1];
    Solve();
    printf("%lld\n",std::max(len,ans));
    return 0;
}
Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏