CSacademy) Tree Nodes Sets

https://csacademy.com/contest/round-36/task/tree-nodes-sets/

N <= 10^5, sum(K) <= 10^5

N개의 노드로 이루어진 트리가 있다. 이 트리의 각각의 노드는 set 이 있는데 처음에는 모두 빈 set이다.

각 노드에서는 K개의 operation 을 한다. operation을 하는 노드의 서브트리의 모든 노드들의 set에

임의의 수 t를 추가하거나 삭제하는 두가지의 operation 이 있고, 이 operation은 root노드(1번 노드가 root이다)

에서부터 시작하여 리프까지 가는 노드 순서대로 행해진다.  이 때 operation 을 모두 완료한 후에 

각 노드마다 set에 존재하는 원소의 개수를 출력하는 문제이다. 물론 set에서 존재하지 않는 원소를 삭제하는

operation은 아무일도 하지않으며, 이미 존재하는 원소를 추가하는 operation또한 아무일도 하지않는다.

이 문제는 보통 dfs를 돌리면서 인자로 현재 노드번호와 set을 주어 구현하려고 생각할 수가 있다.

하지만 한쪽 자식을 갔다 온 뒤 다음 자식으로 가려고할 때 set이 변화 되어 있기 때문에 인자로 set을 줄 때

레퍼런스로 주는 것이 아니라 값을 복사하는 식으로 한다거나, 아니면 레퍼런스로 주되, dfs 를 돌릴 때 지역변수로

set을 백업하는 변수를 두어 한 자식으로 보고 오면 다시 복구 시켜주는 식으로 구현하는 식으로 생각해 볼 수가

있을 것이다. 하지만 문제가 있다. 둘 다 함수가 호출될 때마다 기존에 가지고 있던 set을 복사하여

새롭게 메모리 내에 set을 저장할 공간을 사용한다는 것이다. 그러면 set 에는 최악의 경우

10만개의 원소가 들어가는데 dfs로 깊이 들어갈 때마다 새로운 10만개의 원소를 가진 set을 복사하므로 

만약 연결 리스트 형태의 트리라면 메모리에 할당되는 set들의 원소의 수의 합은 총 O(N^2) 개일 것이다.

정확히는 N*(N+1)/2 개 정도? 아무튼 그래서 메모리가 터지게 된다. 그렇기 때문에 인자로 set은 

call-by-reference 로 하며 절대로 함수내에서 이 변수를 복사하면 안된다. 그렇다면 중요한 것은

한 자식을 보고 왔을 때 전과 같은 상태로 복원만 해주면 되는 것인데 이것은 

현재 노드의 operation에 의해 원래 없었는데 추가된 원소와 원래 있었는데 삭제된 원소를

그때 그때 따로 백업을 해두어 함수가 리턴되기 직전에 다시 복원을 해주는 방법으로 하면 된다.

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int mod = 1e9+7;
    const int inf = 0x3c3c3c3c;
    const long long infl = 0x3c3c3c3c3c3c3c3c;
 
    int ans[100003];
    vector<int> G[100003];
    int N;
    vector<int> oper[100003];
    set<int> stt;
    void dfs(int here, set<int>& st){
        vector<int> rm, add;
        for(int op : oper[here]){
            if(op < 0) {
                auto it = st.find(-op);
                if(it != st.end()) rm.push_back(*it), st.erase(it);
            }
            else {
                auto it = st.find(op);
                if(it == st.end()) add.push_back(op), st.insert(op);
            }
        }
        ans[here] = st.size();
        for(int there : G[here]){
            dfs(there, st);
        }
        for(int it : rm) st.insert(it);
        for(int it : add) st.erase(it);
    }
    int main() {
        cin >> N;
        for(int i = 2; i <= N; i++){
            int p;
            cin >> p;
            G[p].push_back(i);    
        }
        for(int i = 1; i <= N; i++){
            int K;
            cin >> K;
            for(int j = 0 ; j < K; j++){
                int a;
                cin >> a;
                oper[i].push_back(a);
            }
        }
        dfs(1, stt);
        for(int i = 1 ; i <= N; i++) cout << ans[i] << endl;
        return 0;
    }