【题解】[ABC448D] Integer-duplicated Path

zsTree · 2026-03-07 23:17:46 · 题解

获得更好的阅读体验。

题目传送门：AtCoder | Luogu

题意

给定一棵树，共有 N 个点，M 条边。第 i 个点有一个整数 A_i，第 i 条边连接 U_i 和 V_i 两个节点。

求对于所有 k\in[1,N]，从节点 1 走到节点 k 的简单路径上，是否有两个写有相同整数的不同节点。

思路

预处理。

从节点 1 开始 dfs，标记当前节点 u 的整数 A_u 出现过。

如果有一个节点 v(v\ne 1) 的整数 A_v 被标记过，那么从节点 1 到 v 子树中的所有节点的简单路径上都有写有相同整数的两个不同节点。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 2e5 + 10;
int a[N];
vector<int> G[N];
unordered_map<int, bool> vis;
bool ans[N];

void dfs(int u, int fa, bool f) {
    if (f || vis[a[u]]) {
        ans[u] = f = true;
        for (const int& v : G[u])
            if (v != fa)
                dfs(v, u, true);
        return;
    }

    vis[a[u]] = true;
    for (const int& v : G[u])
        if (v != fa)
            dfs(v, u, false);
    vis[a[u]] = false;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;

        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }

    dfs(1, 0, false);
    for (int i = 1; i <= n; i++) cout << (ans[i] ? "Yes" : "No") << '\n';

    return 0;
}