CF1294F 一树三路

· · 题解

Part.0 闲话

更好的观看体验

目前题解区里大多数巨佬都是采用的树形 dp 和暴力等方法，看见没有我这种做法，欢迎指出做法问题或 hack 代码。

Part.1 题意

给定一棵树，选 3 个点 a, b, c，求 a 到 b 的路径与 a 到 c 的路径与 b 到 c 的路径上一共有多少不重复的边。

Part.2 分析

我们不妨把每条边的边权设为 1，这样方便我们计算贡献。

仔细思考一下后，可以发现无论如何，先把树的直径的端点选上最优，而 c 也一定是在某一个距离直径上点最远的点。

但是一个问题诞生了，怎么求这个距离最远的点呢？枚举直径上点再搜的时间复杂度是 O(n^2) 的，肯定会超时。

这时候，前文将边权设为 1 的好处就凸显出来了。

我们可以把所有直径上的边的边权全部设置为 0，然后从直径的某一个端点再次搜索一遍树的直径，那么新直径的另一个端点就是我们要求的 c，起点可以选在直径上的任意一点，因为此时在直径上搜不会增加答案的值。

所以答案就是旧直径的长加新直径的长。

Part.3 代码

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 2e5 + 5;

struct Node {
    int v, w, nxt;
} e[kMaxN << 1];

int n;
int dis, x;
int res, a, b, c;
int hd[kMaxN], cnt = 1;
vector<pair<int, int>> stk, d;

void add(int u, int v) {
    e[++cnt].nxt = hd[u];
    hd[u] = cnt;
    e[cnt].v = v;
    e[cnt].w = 1;
}

void dfs(int u, int fa, int s) {
    if (s >= dis) {
        dis = s;
        if (u != a && u != b && u != c) {
            x = u;
            d = stk;
        }
    }
    for (int i = hd[u]; i; i = e[i].nxt) {
        int v = e[i].v, w = e[i].w;
        if (v == fa) {
            continue;
        }
        stk.push_back({u, i});
        dfs(v, u, s + w);
        stk.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1, a, b; i < n; i++) {
        cin >> a >> b;
        add(a, b);
        add(b, a);
    }
    dis = 0;
    dfs(1, 0, 0);
    a = x;
    dis = 0;
    dfs(x, 0, 0);
    b = x;
    res += dis;
    dis = 0;
    for (auto i : d) {
        e[i.second].w = e[i.second ^ 1].w = 0;
    }
    dfs(x, 0, 0);
    c = x;
    res += dis;
    cout << res << '\n' << a << ' ' << b << ' ' << c << '\n';
    return 0;
}

值得注意的是，一定要使用链式前向星并且把双向的边全部边权赋为 0。因为我太菜了，所以只能开个栈储存直径上的边，事实上可以边搜边赋值。

时间复杂度 O(n)，常数可能有一点大。