「Bzoj 3124」「SDOI2013」直径 (树的直径)

bzoj 3124
题解：对于给定的一棵树，求其直径的长度是多少，以及有多少条边满足所有的直径都经过该边。

第一问直接两次 DFS 求直径。
考虑第二问求直径必须边。
记录

$Ldis$: 从直径左边端点到直径右边点的距离
$Rdis$: 从直径右边端点到直径左边点的距离
$Edis$: 直径上的点的最大偏心距

我们从一个直径端点在直径上开始往右走，若存在$Rdis(i)+Edis(i)=len$，$len$为直径长，那么这里开始后面的就不是必须边。

然后相反地，我们从右往左做一次，然后得出了一个范围$[l,r]$，然后就非常好处理了

#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 = 200000 + 5;

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

    int n, hd[MAXN], en, dd1, dd2, vis[MAXN], zjd[MAXN], cnt;
    LL tmp_dis[MAXN], l_dis[MAXN], r_dis[MAXN], e_dis[MAXN];

    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) {
                tmp_dis[e.v] = tmp_dis[u] + e.w;
                dfs_dis(e.v, u);
            }
        }
    }
    int dfs_vis(int u, int fa) {
        if (u == dd2) return zjd[++cnt] = u, vis[u] = 1, 1;
        for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa) {
                int fl = dfs_vis(e.v, u);
                if (fl && !vis[u]) zjd[++cnt] = u, vis[u] = 1;
            }
        }
        return vis[u];
    }
    void dfs_e(int u, int fa) {
        for (int i = hd[u]; i >= 0; i = ed[i].nxt) {
            edge &e = ed[i];
            if (e.v != fa && !vis[e.v]) {
                dfs_e(e.v, u);
                e_dis[u] = max(e_dis[u], e_dis[e.v] + e.w);
            }
        }
    }

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

        clean();
        scanf("%d", &n);
        for (int u, v, w, i = 1; i < n; ++i) {
            scanf("%d%d%d", &u, &v, &w);
            ins(u, v, w), ins(v, u, w);
        }

        ms(tmp_dis, 0), dfs_dis(1, 0);
        dd1 = 0; for (int i = 1; i <= n; ++i) if (tmp_dis[i] > tmp_dis[dd1]) dd1 = i;
        ms(tmp_dis, 0), dfs_dis(dd1, 0);
        dd2 = 0; for (int i = 1; i <= n; ++i) if (tmp_dis[i] > tmp_dis[dd2]) dd2 = i;

        memcpy(l_dis, tmp_dis, sizeof tmp_dis);

        ms(tmp_dis, 0), dfs_dis(dd2, 0);
        memcpy(r_dis, tmp_dis, sizeof tmp_dis);

        dfs_vis(dd1, 0);
        for (int u = 1; u <= n; ++u) if (vis[u]) dfs_e(u, 0);

        int l = 1;
        for (int i = 1; i <= cnt && l < cnt; ++i) {
            int u = zjd[i];
            if (e_dis[u] && r_dis[u] + e_dis[u] == l_dis[dd2]) break; else ++l;
        }
        int r = cnt;
        for (int i = cnt; i && r > 1; --i) {
            int u = zjd[i];
            if (e_dis[u] && l_dis[u] + e_dis[u] == l_dis[dd2]) break; else --r;
        }

        printf("%lld\n%d\n", l_dis[dd2], l - r);

        return 0;
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}
/*
3
1 2 3
2 3 5

14
1 2 10
1 3 5
1 4 10
1 9 9
9 10 1
9 12 1
3 5 3
5 7 2
5 6 6
7 8 4
3 13 3
13 11 1
13 14 2
*/