[心之碎片][0622] - 巡逻

柿子饼同学

巡逻 link
提交 4 次
3 h

知识点
dp求树的直径 贪心


思路
K == 0, ans0 = 2*(n - 1)
K == 1, 取直径1, ans1 = ans0 - 直径1 + 1
K == 2, 直径上的边权变成 -1, 再算直径2, ans2 = ans1 - 直径2 + 1
这里取反边权是因为, 第二条边如果覆盖了直径, 路程反而会增加这一段的, 别的路径不碍事
求直径就相当于求让路径可以尽可能减小的路程
O(n)

注意点
dfs 不能处理负权树求直径 , 只能用 dp 求, 写的时候 dp 写反了 , 要注意是用 ed 求出 u 的值
证明取直径最优 :

调整法 分两种情况讨论：

一：若选的第一个环与直径无相交的边，则第二个环选直径最优，这等价于第一个环选直径。

二：若选的第一个环与直径有相交的边，将直径与第二个环相交但不与第一个环相交的部分加到第一个环上，答案不变，然后再在第一个环上加上直径上不与第二个环重叠的点，答案增加，因此不如第一个环就直接选直径。

综上，第一个环选直径一定不劣。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;

int n, k, ans;
vector<int> e[N];
int p, q, f[N], d[N];
bitset<N> isd;

void dfs(int u, int pa, int & id){
    for(auto ed : e[u]){
        if(ed == pa) continue;
        f[ed] = u;
        if(isd[u] && isd[ed]) d[ed] = d[u] - 1;
        else d[ed] = d[u] + 1;

        if(d[0] <= d[ed]){
            d[0] = d[ed];
            id = ed;
        }

        dfs(ed, u, id);
    }   
}

void Getd1(){
    d[0] = 0, f[1] = 0, d[1] = 0;
    dfs(1, 0, p);
    d[0] = 0, d[p] = 0, f[p] = 0;
    dfs(p, 0, q);
}

int dp[N], res;
void Getd2(int u, int f){
    for(auto ed : e[u]){
        if(ed == f) continue;
        int w = 1;
        if(isd[ed] && isd[u]) w = -1;
        Getd2(ed, u);
        res = max(res, dp[u] + dp[ed] + w);
        dp[u] = max(dp[u], dp[ed] + w);
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> k;
    for(int i = 1; i < n; i++){
        int x, y;
        cin >> x >> y;
        e[x].emplace_back(y);
        e[y].emplace_back(x);
    }

    ans = 2*(n - 1);
    if(k == 0){
        cout << ans;
        return 0;
    }

    Getd1();   
    ans -= d[0] - 1;
    if(k == 1){
        cout << ans;
        return 0;
    }

    for(int i = q; i; i = f[i]){
        isd[i] = 1;
    }
    Getd2(1, 0);
    ans -= res - 1;
    cout << ans;

    return 0;
}

harryhan123

啊