CF835F Roads in the Kingdom [基环树]

$Roads in the Kingdom$

题目描述见链接 .

---

$color{red}{正解部分}$

将 环 拆成 链, 则 树的直径 只有可能是下图两种情况,

其中 子树 内的最长直径只有可能是上面三种情况,
首先处理每个子树从根节点向下延伸的最长长度, 即 最深深度, 记为 $max\_dep[i]$,

• 记录 $i$ 点 左边连续的通向弯边端点 的 最长链, 记为 $max\_l[i]$,
  $max\_l[i] = max(max\_dep[i]+sum\_l[i], max\_l[i-1])$ .
  同 从左向右再往下 的 最长链, 记为 $max\_r[i]$, 与上方更新方式相同 .
• 记录 $max\_l\_2[i]$ 表示 $i$ 向左再往下 的最长链长度,
  $max\_l\_2[i] = max(max\_dep[i], max\_l\_2[i-1] + B[i-1])$
• 记录 $ml[i]$ 表示 左边最长的订书针形链,
  $ml[i] = max(max\_dep[i]+max\_l\_2[i-1]+B[i-1], ml[i-1])$ .
  $mr[i]$ 同理,

---

• 第一种情况, 断掉 弯边, 此时只能通过 订书针形链 更新答案,
  $Ans = max(max\_l\_2[i-1] + max\_r\_2[i] + B[i])$ .
• 第二种情况, 断掉 直边, 此时既可以通过 订书针形链 更新答案, 又可以通过 桥状链 更新答案,
  $Ans = min(Ans, max(ml[i-1], mr[i], max\_l[i-1]+max\_r[i] + edge_{弯边}.w))$
• 第三种情况, 使用 $子树的直径$ 更新答案 .

---

$color{red}{实现部分}$

#include<bits/stdc++.h>
#define reg register
#define pb push_back
typedef long long ll;

int read(){
        char c;
        int s = 0, flag = 1;
        while((c=getchar()) && !isdigit(c))
                if(c == '-'){ flag = -1, c = getchar(); break ; }
        while(isdigit(c)) s = s*10 + c-'0', c = getchar();
        return s * flag;
}

const int maxn = 4e5 + 10;

int N;
int num0;
int Tmp_1;
int Tmp_2;
int rd[maxn];
int vis[maxn];
int head[maxn];
int is_cir[maxn];

ll Ans;
ll Tmp_3;
ll max_dis;
ll dep[maxn];
ll mr[maxn];
ll ml[maxn];
ll max_l[maxn];
ll max_r[maxn];
ll sum_l[maxn];
ll sum_r[maxn];
ll max_dep[maxn];
ll max_l_2[maxn];
ll max_r_2[maxn];

std::vector <int> A, B;

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

void Add(int from, int to, int w){ edge[++ num0] = (Edge){ head[from], to, w }; head[from] = num0; }

ll Max(ll a, ll b){ return a>b?a:b; }

void Top_sort(){
        std::queue <int> Q;
        for(reg int i = 1; i <= N; i ++) if(rd[i] == 1) Q.push(i);
        while(!Q.empty()){
                int ft = Q.front(); Q.pop();
                for(reg int i = head[ft]; i; i = edge[i].nxt){
                        int to = edge[i].to;
                        if((-- rd[to]) == 1) Q.push(to);
                }
        }
        for(reg int i = 1; i <= N; i ++) if(rd[i] > 1) is_cir[i] = 1, Tmp_1 = i;
}

void DFS_1(int k){ // 将环排成链放进 vector
        vis[k] = 1; A.pb(k);
        for(reg int i = head[k]; i; i = edge[i].nxt){
                int to = edge[i].to;
                if(!vis[to] && is_cir[to]) B.pb(edge[i].w), DFS_1(to);
                if(vis[to] && is_cir[to]) Tmp_2 = edge[i].w;
        }
}

std::vector <int> Hs;

void DFS_2(int k, int rt, ll dis){ // 子树直径
        if(dis > max_dis) max_dis = dis, Tmp_1 = k;
        //printf("%d: %lld
", k, dis);
        vis[k] = 1; Hs.pb(k); for(reg int i = head[k]; i; i = edge[i].nxt){
                int to = edge[i].to;
                if(vis[to] || (is_cir[to] && to != rt)) continue ;
                DFS_2(to, rt, dis + edge[i].w);
        }
}

void DFS_3(int k, int fa){ // 找 max_dep
        max_dep[k] = dep[k];
        for(reg int i = head[k]; i; i = edge[i].nxt){
                int to = edge[i].to;
                if(is_cir[to] || to == fa) continue ;
                dep[to] = dep[k] + edge[i].w;
                DFS_3(to, k);
                max_dep[k] = Max(max_dep[k], max_dep[to]);
        }
}

int main(){
        N = read();
        for(reg int i = 1; i <= N; i ++){
                int u = read(), v = read(), w = read();
                Add(u, v, w), Add(v, u, w); rd[u] ++, rd[v] ++;
        }
        Top_sort(); DFS_1(Tmp_1);
        int size = A.size();
        for(reg int i = 0; i < size; i ++){
                max_dis = 0;
                DFS_2(A[i], A[i], 0);
                for(reg int j = 0; j < Hs.size(); j ++) vis[Hs[j]] = 0;
                Hs.clear();
                DFS_2(Tmp_1, A[i], 0);
                for(reg int j = 0; j < Hs.size(); j ++) vis[Hs[j]] = 0;
                Tmp_3 = Max(Tmp_3, max_dis); DFS_3(A[i], 0);
        }
        for(reg int i = 0; i < size; i ++){
                if(!i){ 
                        ml[i] = max_l_2[i] = max_l[i] = max_dep[A[i]]; 
                        continue ; 
                }
                max_l_2[i] = Max(max_dep[A[i]], max_l_2[i-1] + B[i-1]);
                sum_l[i] = B[i-1] + sum_l[i-1];
                max_l[i] = Max(max_dep[A[i]]+sum_l[i], max_l[i-1]);
                ml[i] = Max(max_dep[A[i]]+max_l_2[i-1]+B[i-1], ml[i-1]);
        } 
        for(reg int i = size-1; i >= 0; i --){
                if(i == size-1){ mr[i] = max_r_2[i] = max_r[i] = max_dep[A[i]]; continue ; }
                max_r_2[i] = Max(max_dep[A[i]], max_r_2[i+1] + B[i]);
                sum_r[i] = B[i] + sum_r[i+1];
                max_r[i] = Max(max_dep[A[i]]+sum_r[i], max_r[i+1]);
                mr[i] = Max(max_dep[A[i]]+max_r_2[i+1]+B[i], mr[i+1]);
        }
        Ans = 0;
        for(reg int i = 1; i < size; i ++) Ans = Max(Ans, max_l_2[i-1] + max_r_2[i] + B[i-1]);
        for(reg int i = 1; i < size; i ++){
                ll maxx = max_l[i-1] + max_r[i] + Tmp_2;
                maxx = Max(maxx, ml[i-1]);
                maxx = Max(maxx, mr[i]);
                Ans = std::min(Ans, maxx);
        }
        std::cout << Max(Ans, Tmp_3);
        return 0;
}