백준15978 족보

작성일 | In

문제 링크

  • http://icpc.me/15978

문제 출처

  • 2018 KOI 고등부 4번

사용 알고리즘

  • 유니온 파인드

시간복잡도

  • $O(N \log N)$

풀이

리프 정점들의 번호는 고정되어있기 때문에, 각 정점 아래에 달려있는 리프 정점들의 집합은 서로 포함 관계이거나 독립적이라는 것을 관찰합시다.

풀이 설명의 편의를 위해 몇 가지 기호/집합을 정의하겠습니다.

  • 정점 $v$ 아래에 달려있는 리프 정점들의 집합을 $S(v)$라고 정의합시다.
  • 트리 $T$에 속한 정점 $v_1, v_2, \cdots$에 대해, $S(v_i)$들의 multiset을 $S’(T)$라고 합시다.

어떤 정점 $Q$와 그 정점의 부모 정점 $P$를 합치는 것은 $S’(T)$에서 $S(Q)$를 제거하는 것을 의미합니다. 그러므로 $T$에서 0번 이상의 단위훼손을 통해 $T’$을 만들 수 있다는 것과 $S’(T’) \subset S’(T)$은 동치입니다.
어떤 트리 $T$에서 0번 이상의 단위훼손을 통해 트리 $A, B$를 만들 수 있는지 판별하는 것은 $S’(A) \subset S’(T)\ and\ S’(B) \subset S’(T)$와 동치이고, 결국 $S’(A) \cup S’(B) \subset S’(T)$인 $T$가 존재하는지 확인하는 문제가 됩니다.

이것을 빠르게 확인하는 방법으로는, 트리 $A, B$에 속한 정점들을 모아서 집합의 크기가 작은 것부터 Union하면서 모순이 없는지(Union-Find에서 현재 집합의 크기와 정점 $v$ 밑에 있는 리프의 개수가 같은지) 판별하면 됩니다.

정점(집합)을 정렬하는데 가장 많은 시간을 사용하므로 $O(N \log N)$에 문제를 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/******************************
Author: jhnah917(Justice_Hui)
g++ -std=c++17 -DLOCAL
******************************/

#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) (lower_bound(all(v), x) - v.begin())
using namespace std;

using uint = unsigned;
using ll = long long;
using ull = unsigned long long;
using PII = pair<int, int>;

struct UnionFind{
    int P[303030], S[303030];
    UnionFind(){ iota(P, P+303030, 0); fill(S, S+303030, 1); }
    int find(int v){ return v == P[v] ? v : P[v] = find(P[v]); }
    void merge(int u, int v){ u = find(u); v = find(v); if(u != v) S[v] += S[u], P[u] = v; }
    int sz(int v){ return S[find(v)]; }
};

int N, M, K;

struct Tree{
    int root;
    int id[303030], cnt[303030];
    vector<int> G[303030];
    void setParent(int v, int p){
        if(!p) root = v;
        else G[p].push_back(v);
    }
    void dfs(int v){
        if(v <= K) id[v] = v, cnt[v] = 1;
        for(auto i : G[v]) dfs(i), id[v] = id[i], cnt[v] += cnt[i];
    }
    void dfs(){ dfs(root); }
} T1, T2;
UnionFind uf;

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M >> K;
    for(int i=1, p; i<=N; i++) cin >> p, T1.setParent(i, p);
    for(int i=1, p; i<=M; i++) cin >> p, T2.setParent(i, p);
    T1.dfs(); T2.dfs();

    vector<PII> vec;
    for(int i=K+1; i<=N; i++) if(T1.G[i].size() > 1) vec.emplace_back(T1.cnt[i], i);
    for(int i=K+1; i<=M; i++) if(T2.G[i].size() > 1) vec.emplace_back(T2.cnt[i], i+303030);
    sort(all(vec));

    for(const auto &i : vec){
        Tree &T = i.y < 303030 ? T1 : T2;
        int nd = i.y < 303030 ? i.y : i.y - 303030;
        for(const auto &j : T.G[nd]) uf.merge(T.id[nd], T.id[j]);
        if(uf.sz(T.id[nd]) > i.x){ cout << "NO"; return 0; }
    }
    cout << "YES";
}