Codeforces 835 F Roads in the Kingdom(树形dp)

时间：2021-08-16 15:15:59

F. Roads in the Kingdom(树形dp)

题意：

给一张n个点n条边的无向带权图

定义不便利度为所有点对最短距离中的最大值

求出删一条边之后，保证图还连通时不便利度的最小值

$n <= 2e5 $

\(w_i <= 1e9\)

思路:树形dp

这个图是一个环上挂着很多颗树，首先把这个环处理出来，

删边只能在环上进行，所以可以先求出以环上每个点为根的树的直径和最大深度dep，

答案来源分为二种

  • 树内部两点最远距离 -> 直径 (树形dp 或者 两次bfs)
  • 两棵树深度最大的两点配对

假设环长度为\(k\),把环变成一个序列\(a_1,a_2,...,a_k\) 令\(a_0 = a_k\)

选择\(a_0\)做起点，用\(s_i\)表示第\(i\)个点到起点的距离

考虑每次断开的边为\(e(a_{i-1},a_i)\),那么答案分为三种情况

  • 序列\(1\)到\(i-1\)中选两个点配对取最大值
  • 序列\(i\)到\(k\)中选两个点配对取最大值
  • 前后各取一个点配对取最大值

计算第一种情况

假设取的两个点为\(1<=x<y<=i-1\),

则距离\(d = dep[x] + dep[y] + dis[x][y] = dep[x] - s[x] + dep[y] + s[y]\)

这样我们只需要顺序枚举维护\(dep[x] - s[x]\)的最大值即可

同理，第二种情况只需要逆序枚举维护\(dep[x] + s[x]\)的最大值即可

考虑第三种情况 假设取的点为\(1 <= x <= i - 1 , i <= y <= k\)

则距离\(d = dep[x] + dep[y] + dis[x][y] = dep[x] + dep[y] + s[k] - (s[y] - s[x])\)

$d = (dep[x] + s[k] + s[x]) + (dep[y] - s[y]) $

同理，顺序可算出第一部分最大值，逆序可以算出第二部分最大值

最后在删边后三种情况的最大值里取最小值再和树内部直径比较即可

#include<bits/stdc++.h>

#define LL long long

#define P pair<int,int>

#define ls(i) seg[i].lc

#define rs(i) seg[i].rc

using namespace std;

const int N = 2e5 + 10;

const LL inf = 1e18;

int read(){

    int x = 0;

    char c = getchar();

    while(c < '0' || c > '9') c = getchar();

    while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();

    return x;

}

vector<P>G[N];

int n,k;

int a[N],pa[N],e[N];

LL s[N],dep[N],ans;

void dfs(int u,int fa){

    pa[u] = fa;

    for(auto v:G[u]){

        if(v.first == fa) continue;

        if(pa[v.first] == 0) {

                e[v.first] = v.second;

                dfs(v.first,u);

        }

        else if(!k){

            int x = u;

            a[0] = v.first,s[1] = v.second;

            while(x != v.first) {

                    a[++k] = x,s[k+1] = s[k] + e[x],x = pa[x];

            }

            a[++k] = v.first;

        }

    }

}

void dp(int u){

    pa[u] = 0;

    for(auto v:G[u]){

        if(pa[v.first] != 0){

            dp(v.first);

            ans = max(ans,dep[v.first] + v.second + dep[u]);

            dep[u] = max(dep[u], dep[v.first] + v.second);

        }

    }

}

LL sL[N],sR[N],L[N],R[N];///把环变成序列，断开的边左边配对，右边配对，左右配对的最大值

int main(){

    int u,v,w;

    n = read();

    for(int i = 1;i <= n;i++){

        u = read(),v = read(),w = read();

        G[u].push_back(P(v,w));

        G[v].push_back(P(u,w));

    }

    k = 0;

    ans = 0;

    dfs(1,-1);

    for(int i = 1;i <= k;i++) pa[a[i]] = 0;

    for(int i = 1;i <= k;i++) dp(a[i]);

    LL mx = -inf;

    L[0] = sL[0] = -inf;

    for(int i = 1;i <= k;i++){

        sL[i] = max(sL[i-1],dep[a[i]] + s[i] + mx);

        L[i] = max(L[i-1],dep[a[i]] + s[k] + s[i]);

        mx = max(mx, dep[a[i]] - s[i]);

    }

    sR[k+1] = R[k+1] = mx = -inf;

    for(int i = k;i >= 1;i--){

        sR[i] = max(sR[i+1],dep[a[i]] - s[i] + mx);

        R[i] = max(R[i+1],dep[a[i]] - s[i]);

        mx = max(mx, dep[a[i]] + s[i]);

    }

    LL tmp = inf;

    for(int i = 1;i <= k;i++) tmp = min(tmp,max(L[i-1]+R[i],max(sL[i-1],sR[i])));

    cout<<max(ans,tmp)<<endl;

    return 0;

}

相关文章