「Bzoj 1912」「Apio2010」巡逻 (树的直径，负权直径)

发表于 | 分类于 | | + s

BZOJ 1912
题意：给你一棵$n$点$n-1$边的树，要从$1$开始出发走遍所有边然后回到$1$，现在你可以加$K(1 \leq K \leq 2)$条边，并且加的边正好走一次，求出最小的路程。

明显如果不加边答案即为$2(n-1)$。
考虑加一条边情况：此时加一条边在$(x,y)$之间，相当于使答案少了$dis(x,y)-1$。即只走这条边不用回溯$x,y$之间的边。我们想要答案最小，那么$dis(x,y)$要最大，所以$x,y$是直径的两个端点。

加两条边的情况，可以考虑先将直径加边，然后再将直径上的边删除，然后树变为森林，求每棵树的直径取最大值。但不一定第一条边加在直径最优，这个贪心是错的，但是分还挺多。
我们考虑第一条边还是先加直径，但是我们之后将直径上的边权都改为$-1$，然后再对树求一下直径，然后答案减去直径长-1。
因为-1相当于还原之前选的直径上的边，即这个位置还是走两次。感觉和Bzoj 1050类似。
这里有负权就不能两次搜索找直径了，所以要用DP，DP有点类似点分治。
最开始原图还是最好用两次搜索，这样方便找到端点。

知识点
1、负权时不能用搜两次找直径，要用DP
2、想到的做法没有完全落实不要认为是对的，但是迫不得已可以写来骗分

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db long double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 100000 + 5;

    struct edge {
        int v, w, nxt;
    } ed[MAXN * 2];

    int n, K, en, hd[MAXN], ans;
    int zj1, zj2, dis[MAXN], hh;

    void ins(int u, int v, int w) {ed[++en] = (edge){v, w, hd[u]}, hd[u] = en;}

    void dfs_dis(int u, int fa) {
        for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa) {
                dis[e.v] = dis[u] + e.w;
                dfs_dis(e.v, u);
            }
        }
    }
    int dfs_bj(int u, int fa) {
        if (u == zj2) return 1;
        int fl = 0;
        for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa) {
                int gg = dfs_bj(e.v, u);
                fl |= gg;
                if (gg) ed[i].w = ed[i ^ 1].w = -1;
            }
        }
        return fl;
    }
    void dfs_dp(int u, int fa) {
        for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa) {
                dfs_dp(e.v, u);
                hh = max(hh, dis[e.v] + e.w + dis[u]);
                dis[u] = max(dis[u], dis[e.v] + e.w);
            }
        }
    }

    void clean() {
        en = -1, ms(hd, -1);
    }
    int solve() {

        clean();

        scanf("%d%d", &n, &K), ans = (n - 1) * 2;
        for (int x, y, i = 1; i < n; ++i) {
            scanf("%d%d", &x, &y);
            ins(x, y, 1), ins(y, x, 1);
        }

        ms(dis, 0), zj1 = 0, dfs_dis(1, 0);
        for (int i = 1; i <= n; ++i) if (dis[i] > dis[zj1]) zj1 = i;
        ms(dis, 0), zj2 = 0, dfs_dis(zj1, 0);
        for (int i = 1; i <= n; ++i) if (dis[i] > dis[zj2]) zj2 = i;

        ans = ans - dis[zj2] + 1;

        if (K == 1) return printf("%d\n", ans), 0;

        dfs_bj(zj1, 0);

        ms(dis, 0), hh = 0, dfs_dp(1, 0);

        ans = ans - hh + 1;

        printf("%d\n", ans);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
------ 本文结束 ------