题解 P3304 [SDOI2013]直径

· · 题解

update 2020.8.6 题解补充了原先没有的特判。

update 2020.9.27 原题解有特殊情况没有考虑。

我阐释另一种更加简洁、简单的方法。

题意简述

给定一棵无向带权无根树，有 n 个节点（1\leq n \leq 2\times10^5）。

求出其直径长，所有直径都经过的边的数量。

题解

关于直径的询问，可以从直径的性质入手。

第一问可以直接用 BFS 求出直径。

第二问：

可以发现，直径的公共部分，一定是连在一起的。

其他题解都是从两端判的。

我的方法是，第一问求出的直径的长 len ，及其直径上的所有边的权值减一，再求一次直径的长 clen，两次直径长的差 len-clen 就是第二问的答案。

证明：

假设答案为 x，即所有直径都会经过共同的 x 条边。

如果对任意一条直径上的边权全部减去 1，那么意味所有直径共同的 x 条边都会减去 1。

即再求一次直径后，新直径一定是原直径的值减去 x（因为减去了所有公共边的长度）。

至此，该解法的核心思路已经阐述完毕。除了实现，有两个特殊情况需要考虑进去，读者可以尝试自行思考。

细节注意

记录直径的路径可以用 BFS，开一个 pre 数组。

每次更新 dis 时，pre 记录当前在邻接表数组的下标。

遍历直径路径直接 for 回溯。

遍历用到了成对变换的技巧。在蓝书上的 \text{P9} 页有讲。注意 tot 初始值要赋值成 1。

更具体的可以参考代码。

还有一种特殊的情况。

5
1 2 2
1 3 2
1 4 1
4 5 1

这组数据的输出应该是 4 和 0。

因为这棵树中，有 3 个不同的直径，而这些直径两两之间是没有公共边的。

当存在 3 条链 a,b,c，任意两者的和为直径时，该情况成立。

解决方法：遍历直径时，找出一个当前权值和为直径长一半的点，然后权值减完后，以这个点为根，遍历一遍树，计算以根为起点的链最大长度。如果和直径长一半相等，那么就就存在该特殊情况。

还有一种特殊情况。

8
1 2 2
2 3 1
3 4 1
2 5 1
5 6 1
6 7 1
4 8 1

感谢 @zhangjianjunab 提供的 Hack 数据。

手玩一下可以发现，这棵树只有一个直径，且直径上的边权都是 1，更新直径时，边变成 0，再次求直径时就求原本不是直径的链。

解决方法：把所有边权都扩大相同倍。这样就避免了 1 的情况。

然而洛谷和 Acwing 上没这两个情况的数据。

代码

特殊情况的处理稍微有一点点乱，见谅。

#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int MAXN = 400010;
const int MAXM = 100010;
const int MAXINT = 2147483647;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;

int n, m, k;
int ans, tot = 1, cnt;
ll clen, mlen;

int a[MAXN];
int head[MAXN], pre[MAXN];
ll dis[MAXN];

string s;

inline int read() {
    int s = 0, f = 1;
    char ch = getchar();
    while ('0' > ch || ch > '9') {if (ch == '-') f = -1; ch = getchar();}
    while ('0' <= ch && ch <= '9') {s = (s << 3) + (s << 1) + ch - 48; ch = getchar();}
    return s * f;
}

struct edge {
    int to, next;
    ll w;
}e[MAXN * 2];

void add_edge(int x, int y, ll w) {
    e[++tot].to = y;
    e[tot].w = w;
    e[tot].next = head[x];
    head[x] = tot;
    return;
}

void Init() {
    for (int i = 1; i <= n; i++) {
        dis[i] = 1ll << 60;
        pre[i] = 0;
    }
    return;
}

int bfs(int s) {//求直径，并用 pre 记录直径信息。
    Init();
    dis[s] = 0;
    pre[s] = 0;
    queue<int> q;
    q.push(s);
    int res = 1;
    while (q.size()) {
        int x = q.front();
        q.pop();
        for (int i = head[x]; i; i = e[i].next) {
            int y = e[i].to;
            ll w = e[i].w;
            if (dis[y] != 1ll << 60) continue;
            dis[y] = dis[x] + w;
            pre[y] = i;
            if (dis[y] > dis[res]) res = y;
            q.push(y);
        }
    }
    return res;
}

void dfs(int x, int fa) { //dp求直径，来求修改后的树的直径。
    for (int i = head[x]; i; i = e[i].next) {
        int y = e[i].to;
        ll w = e[i].w;
        if (y == fa) continue;
        dfs(y, x);
        clen = max(clen, dis[x] + dis[y] + w);
        dis[x] = max(dis[x], dis[y] + w);
    }
    return;
}

void dfs1(int x, int fa) {//判断特殊情况最长链的长度。
    for (int i = head[x]; i; i = e[i].next) {
        int y = e[i].to, w = e[i].w;
        if (y == fa) continue;
        dfs1(y, x);
        dis[x] = max(dis[x], dis[y] + w);
        mlen = max(dis[x], mlen);
    }
    return;
}

int main(){
    int T;
    scanf("%d", &n);
    for (int i = 1, x, y; i < n; i++) {
        ll w;
        scanf("%d%d%lld", &x, &y, &w);
        w *= 1000;
        if (!w) exit(0);
        add_edge(x, y, w);
        add_edge(y, x, w);
    }

    int p = bfs(1);
    int q = bfs(p);
    ll len = dis[q];
    printf("%lld\n", len / 1000);
    int mid, sum = 0;
    for (; pre[q]; q = e[pre[q] ^ 1].to) {//修改直接，并记录直径中点。
        --e[pre[q]].w;
        --e[pre[q] ^ 1].w;
        sum += e[pre[q]].w;
        if (sum == len / 2) mid = e[pre[q]].to; 
    }
    int ok = 0;
    memset(dis, 0, sizeof(dis));
    dfs1(mid, 0);
    if (mlen == len / 2) ok = 1;
    memset(dis, 0, sizeof(dis));
    dfs(1, 0);
    if (len / 1000 % 2 == 0 && ok) {//特判。
        printf("0\n");
    }
    else {
        printf("%lld\n", len - clen);
    }
    return 0;
}
/*
8
1 2 2
2 3 1
3 4 1
2 5 1
5 6 1
6 7 2
4 8 2

7
1 2 2
1 3 2
1 4 1
4 5 1
1 6 2
1 7 2
*/

日供一卒，功不唐捐。