CS round--36

https://csacademy.com/contest/round-36/summary/

C题是一个贪心，最坏情况是，一开始肯定是每一对袜子都抽一个，然后就需要N个袜子了。后面的情况就是相同的了。

就是，整个数组变成了1、1、1、1、1、1、1、1、1这样，之后任意拿一个袜子，都会增加1pair，然后1-->0，很明显第二次拿应该在刚才那个地方拿，使得0-->1，这样pair数不增加，然后又回到1、1、1、1、1、...这样的状态。所以以后就是在同一种颜色里面操作就好了。

对于本来是奇数的情况，全部拿完是最坏的情况，因为有一个袜子匹配不了。

对于本来是偶数的情况，拿奇数个是最坏的情况，因为这样也有一个袜子匹配不了。

然后直接贪心。

D题是一个树的dfs

用一个数组表示当前的集合，cnt表示集合的大小。

每个节点都有insert, erase操作，dfs的时候，回溯的时候反向更新就好（就是本来insert的变成erase）

但是要注意它时候有这个操作，就是本来是erase的，然而当前集合压根就没这个元素，这是有一个没用的操作。

回溯的时候不要重新insert就好

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
const int maxn = 1e5 + 20;
struct Edge {
    int u, v, tonext;
}e[maxn * 2];
int first[maxn], num;
struct Node {
    int val;
    bool isUsed;
    Node(int _val, int _isUsed) {
        val = _val, isUsed = _isUsed;
    }
};
vector<Node> vc[maxn];
void addEdge(int u, int v) {
    e[num].u = u, e[num].v = v, e[num].tonext = first[u];
    first[u] = num++;
}
int ans[maxn];
bool in[maxn];
int cnt;
void dfs(int cur) {
    for (int i = 0; i < vc[cur].size(); ++i) {
        int val = vc[cur][i].val;
        if (val > 0) {
            if (in[val]) continue;
            in[val] = true;
            cnt++;
            vc[cur][i].isUsed = true;
        } else {
            val = -val;
            if (!in[val]) continue;
            in[val] = false;
            cnt--;
            vc[cur][i].isUsed = true;
        }
    }
    ans[cur] = cnt;
    for (int i = first[cur]; ~i; i = e[i].tonext) {
        dfs(e[i].v);
    }
    for (int i = 0; i < vc[cur].size(); ++i) {
        if (vc[cur][i].isUsed == false) continue;
        int val = vc[cur][i].val;
        if (val > 0) {
            assert(in[val] == true);
            in[val] = false;
            cnt--;
        } else {
            val = -val;
            in[val] = true;
            cnt++;
        }
    }
}
void work() {
    memset(first, -1, sizeof first);
    int n;
    cin >> n;
    for (int i = 1; i <= n - 1; ++i) {
        int u;
        cin >> u;
        addEdge(u, i + 1);
    }
    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k;
        while (k--) {
            int val;
            cin >> val;
            vc[i].push_back(Node(val, false));
        }
    }
    dfs(1);
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << endl;
    }
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
//    IOS;
    work();
    return 0;
}