AtCoder ABC448_D: D - Integer-duplicated Path Editorial

305 字

2 分钟

AtCoder ABC448_D: D - Integer-duplicated Path Editorial

2026-03-12

次阅读

算法

AtCoder

/

算法

题目链接#

https://atcoder.jp/contests/abc448/tasks/abc448_d

题目大意#

给定一棵有 $N$ 个节点的树，第 $i$ 个节点上写着一个整数 $A_i$ 。

对于每个 $k=1,2,\dots,N$ ，考虑树上从节点 $1$ 到节点 $k$ 的唯一路径，判断这条路径上是否存在两个不同节点写着相同的整数。

如果存在，输出 Yes；否则输出 No。

解题思路#

如果用 BFS 来为每个节点维护一个 set 集合的话，毫无疑问会 MLE，所以我们要使用 DFS。对树上的点进行遍历，具体做法就是到达一个点后，先判断它的父节点是否已经重复；如果已经重复，就直接标记即可；如果没有重复，就用 unordered_map 统计这个点的值出现的次数，判断当前路径上是否出现重复，再继续 DFS，回溯时记得在 map 上减掉这个值的数量即可。

代码实现#

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N=2e5+10;
4
int a[N];
5
vector<int> q[N];
6
bool success[N];
7
unordered_map<int, int> m;
8
int n, u, v;
9
void dfs(int u, int fa){
10
    for(int t:q[u]){
11
        if(t==fa) continue;
12
        m[a[t]]++;
13
        if(success[u]) success[t]=true;
14
        if(m[a[t]]>=2) success[t]=true;
15
        dfs(t, u);
16
        m[a[t]]--;
17
    }
18
}
19
int main(){
20
    scanf("%d", &n);
21
    for(int i=1;i<=n;i++) scanf("%d", &a[i]);
22
    for(int i=1;i<=n-1;i++){
23
        scanf("%d%d", &u, &v);
24
        q[u].push_back(v), q[v].push_back(u);
25
    }
26
    m[a[1]]++;
27
    dfs(1, -1);
28
    for(int i=1;i<=n;i++){
29
        if(success[i]==false) printf("No\n");
30
        else printf("Yes\n");
31
    }
32
    return 0;
33
}