题解 CF1675F Vlad and Unfinished Business

· · 题解

Description

Vlad 和 Nastya 住在一个有着 n 栋房子和 n-1 条路的城市。你可以把这座城市理解成一棵树。

Vlad 住在 x 号房里，Nastya 住在 y 号房里。Vlad 打算去拜访 Nastya。然而，他想起来在拜访 Nastya 之前还有 k 件事要做，第 i 件事要在第 a_i 号房子里完成。可以以任何顺序办事，办事不需要时间。Vlad 可以用一分钟从一个房子去到与之有路连接的另一个房子。

求 Vlad 最少要用多久才能办完所有事并来到 Nastya 家。

Solution

我们以 Vlad 家为根节点，那么我们最后再去 Nastya 家所在的子树。因为如果先去了 Nastya 家那边，还得再回 Vlad 家去别的地方办事，这样就浪费了时间，因为最后还得去 Nastya 家。

因此我们每下到一个结点，就判断这个结点一下是否还有事情要办，如果有事就下去办，如果 Nastya 在那个子树就最后再去。

Code

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int to[200005], fa[200005];
bool task[200005];
vector<int> tr[200005];
bool dfs1(int x) {//建立树结构
    for (int i = 0; i < tr[x].size(); i++) {
        int &go = tr[x][i];
        if (go == fa[x])
            continue;
        fa[go] = x;
        task[x] |= dfs1(go);
    }
    return task[x];
}
bool dfs2(int x, int y) {//找到 Nastya 家
    if (x == y)
        return 1;
    for (int i = 0; i < tr[x].size(); i++) {
        int &go = tr[x][i];
        if (go == fa[x])
            continue;
        if (dfs2(go, y)) {
            to[x] = go;
            return 1;
        }
    }
    return 0;
}
int dfs3(int x) {//正式行动
    int ans = 0;
    for (int i = 0; i < tr[x].size(); i++) {
        int &go = tr[x][i];
        if (go == fa[x])
            continue;
        if (to[x] != go && task[go])
            ans += dfs3(go) + 2;
    }
    if (to[x] != -1)
        ans += dfs3(to[x]) + 2;
    return ans;
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        memset(task, 0, sizeof(task));
        memset(to, -1, sizeof(to));
        memset(fa, -1, sizeof(fa));
        int n, k, x, y;
        scanf("%d%d%d%d", &n, &k, &x, &y);
        for (int i = 1; i <= k; i++) {
            int a;
            scanf("%d", &a);
            task[a] = 1;
        }
        for (int i = 1; i < n; i++) {
            int u, v;
            scanf("%d%d", &u, &v);
            tr[u].emplace_back(v);
            tr[v].emplace_back(u);
        }
        dfs1(x);
        dfs2(x, y);
        int ans = dfs3(x), now = x;
        while (now != y) {//因为 dfs3 最后会回到根节点，因此要减去两人家之间的距离
            now = to[now];
            ans--;
        }
        printf("%d\n", ans);
        for (int i = 1; i <= n; i++)
            tr[i].clear();
    }
    return 0;
}