CSAcademy Round #36 : D. Tree Nodes Sets

Cよりこっちの方が簡単でない？
https://csacademy.com/contest/round-36/task/tree-nodes-sets/

問題

根付き木が与えられる。
各頂点は整数の集合を保持できるものとする。初期状態ではいずれも空である。
各頂点にはクエリが設定されており、それらはその頂点のSubTree内の頂点が持つ整数集合に、整数を追加するまたは削除するものである。

各頂点に対し、それらの祖先の頂点から順にクエリを実行してきた状態において、整数集合の要素数を求めよ。

解法

整数の集合を持ちDFSしていく。
もし新たな頂点に突入して、整数集合に値の追加・削除をしたのであれば、その内容を覚えておき、最後SubTreeの探索をした後関数を抜ける際、追加・削除を戻してあげればよい。

int N;
int P[101010];
vector<int> E[101010];
set<int> S;
int ret[101010];
vector<int> O[101010];

void dfs(int cur) {
	set<int> add,del;
	
	FORR(r,O[cur]) {
		if(r<0) {
			if(S.count(-r)) {
				del.insert(-r);
				S.erase(-r);
			}
		}
		else {
			if(S.count(r)==0) {
				add.insert(r);
				S.insert(r);
			}
		}
	}
	ret[cur]=S.size();
	FORR(e,E[cur]) dfs(e);
	FORR(r,add) S.erase(r);
	FORR(r,del) S.insert(r);
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x;
		P[i+1]=x-1;
		E[x-1].push_back(i+1);
	}
	FOR(i,N) {
		cin>>x;
		FOR(j,x) cin>>y, O[i].push_back(y);
	}
	dfs(0);
	FOR(i,N) cout<<ret[i]<<endl;
	
}

まとめ

なんか似た問題見たことあったな。