题目链接：https://www.luogu.com.cn/problem/P3629

题目大意：给定一棵树 , 给它增加 1 到 2 条边 , 且新增的边只能走一次 , 使得从 \(1\) 号节点出发 , 遍历其他所有点再回来的总路径最小

solution

首先 , 如果 \(k = 1\) 时 , 显然如果连接一条从 \(a_i\) 到 \(b_i\) 的边 , 则从 \(a_i\) 到 \(b_i\) 之间的路径将只要走 1 次 , 那么总路程将会减少 \(dist(a_i, b_i) - 1\) , 要使总路程最小 , 那么 $dist(a_i, b_i) $ 应该最大 , 显然应该连接这棵树直径的两端

如果 \(k = 2\) 时 , 则主要考虑第二条边该怎么连 , 如果连接一条从 \(a_j\) 到 \(b_j\) 的边 , 那么从 \(a_j\) 到 \(b_j\) 只要走一次 , 但第二次连边组成的环与第一次连边组成的环的重叠部分的长度 \(dis\) 要走两次 , 总路程将会减少 \(dist(a_j, b_j) - dis - 1\) , 这时候有一个非常巧妙的方法 , 将第一次连边组成的环上的边的权值取反 , 再求这棵树上的直径的长度即为上式的最大值

时间复杂度 : \(O(n)\)

一个提醒 : 当树上边权有为负数时 , 不能用两次搜索求直径 , 例如下图 , 从 4 可到达最远为 5 ,

但 5 并不是直径的端点 , 具体原因可以结合两次搜索的原理得出

code

#include<bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &FF) {
    int RR = 1; FF = 0; char CH = getchar();
    for(; !isdigit(CH); CH = getchar()) if(CH == '-') RR = -RR;
    for(; isdigit(CH); CH = getchar()) FF = FF * 10 + CH - 48;
    FF *= RR;
}
inline void file(string str) {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
}
const int N = 5e5;
int n, k, lg, lt[N], vis[N], cl[N], f[N];
int now, fst[N], nxt[N], num[N], wi[N], d[N], ans = INT_MIN;
void add(int u, int v) {
    nxt[++now] = fst[u], fst[u] = now, num[now] = v, wi[now] = 1;
    nxt[++now] = fst[v], fst[v] = now, num[now] = u, wi[now] = 1;
}
int get_longest(int xi) {
    int res = 0, id = 0;
    queue<pair<int, int> > qi;
    for(int i = 1; i <= n; i++) lt[i] = i, vis[i] = 0;
    qi.push(make_pair(xi, 0));
    while(!qi.empty()) {
        pair<int, int> pi = qi.front(); qi.pop();
        vis[pi.first] = 1;
        if(pi.second > res) res = pi.second, id = pi.first;
        for(int i = fst[pi.first]; i; i = nxt[i])
            if(!vis[num[i]]) {
                lt[num[i]] = pi.first;
                qi.push(make_pair(num[i], pi.second + wi[i]));
            }
    }
    return id;  
}
void getlength_bfs() {
    int li = get_longest(1), ri = get_longest(li);
    cl[ri] = 1;
    while(lt[ri] != ri) {
        ri = lt[ri];
        cl[ri] = 1, lg++;
    }
}
void circle_mark() {
    for(int i = 1; i <= n; i++)
        if(cl[i]) {
            for(int j = fst[i]; j; j = nxt[j])
                if(cl[num[j]]) wi[j] = -1;
        }
    for(int i = 1; i <= n; i++) vis[i] = 0;
}
void getlength_dp(int xi) {
    vis[xi] = 1;
    for(int i = fst[xi]; i; i = nxt[i])
        if(!vis[num[i]]) {
            getlength_dp(num[i]);
            f[xi] = max(f[xi], d[xi] + d[num[i]] + wi[i]);
            d[xi] = max(d[xi], d[num[i]] + wi[i]);
        }
}
int main() {
    //file("");
    int u, v;
    read(n), read(k);
    for(int i = 1; i < n; i++)
        read(u), read(v), add(u, v);
    getlength_bfs();
    if(k == 1)
        cout << (n - 1 - lg) * 2 + lg + 1 << endl;
    else {
        circle_mark(); getlength_dp(1);
        for(int i = 1; i <= n; i++) ans = max(ans, f[i]);
        cout << (n - 1 - lg) * 2 + lg + 1 - ans + 1 << endl;
    }
    return 0;
}

【APIO2010】巡逻