rendered paste body#include <iostream>#include <fstream>#include <vector>#include <set>#include <list>using namespace std;typedef int number;struct monkey { monkey() : parent(0) ,r(0) ,left(0) ,right(0) { } number right; number left; number id; monkey* parent; set<number> monkeys; list<number> un; number r;};struct event { number monkey; number second; };monkey * find(monkey * a){ if(a==a->parent)return a; else { monkey * tmp=find(a->parent); a->parent=tmp; return tmp; }}void gunion(monkey * a,monkey * b){ monkey * ga,* gb; ga=find(a); gb=find(b); list<int>::iterator it; if(gb!=ga) { if(ga->r == gb->r) { gb->un.splice(gb->un.begin(),ga->un); ga->parent=gb; gb->r++; } else if( ga->r < gb->r) { gb->un.splice(gb->un.begin(),ga->un); ga->parent=gb; } else if(ga->r > gb->r) { ga->un.splice(ga->un.begin(),gb->un); gb->parent=ga; } }}vector<event> events;int main(){ //fstream in; //in.open("mal1.in"); number * answer=new number[200001]; monkey * G=new monkey[200001]; for(int i=0;i<=200000;i++) { answer[i]=0; G[i].parent=&G[i]; G[i].id=i; G[i].un.push_back(i); } int N,M; scanf("%d %d",&N,&M); for(int i=1;i<=N;i++) { int l,r; scanf("%d %d",&l,&r); if(l!=-1) { G[i].monkeys.insert(l); G[i].left=l; } if(r!=-1) { G[i].monkeys.insert(r); G[i].right=r; } } for(int i=1;i<=M;i++) { int who,hand; scanf("%d %d",&who,&hand); if(hand==1) { G[who].monkeys.erase(G[who].left); } if(hand==2) { G[who].monkeys.erase(G[who].right); } event tmp; tmp.monkey=who; tmp.second=hand; events.push_back(tmp); } bool * visited=new bool[N+1]; for(int i=0;i<=N;i++)visited[i]=0; list<int> bfs; bfs.push_back(1); monkey* start = &G[1]; for(int i=1;i<=N;i++) { set<number>::iterator neigh; neigh=G[i].monkeys.begin(); while(neigh!=G[i].monkeys.end() ) { gunion(&G[*neigh],&G[i]); neigh++; } } list<number>::iterator it; it=G[find(&G[1])->id].un.begin(); while(it!=G[find(&G[1])->id].un.end()) { answer[*it]=-1; it++; } G[G[1].parent->id].un.clear(); for(int i=M-1;i>=0;i--) { event tmp=events[i]; if(tmp.second==1) { if(find(&G[tmp.monkey]) != find(&G[G[tmp.monkey].left])) { gunion(&G[tmp.monkey],&G[G[tmp.monkey].left]); } } if(tmp.second==2) { if(find(&G[tmp.monkey]) != find(&G[G[tmp.monkey].right])) { gunion(&G[tmp.monkey],&G[G[tmp.monkey].right]); } } it=G[find(&G[1])->id].un.begin(); while(it!=G[find(&G[1])->id].un.end()) { answer[*it]=i; it++; } G[G[1].parent->id].un.clear(); } for(int i=1;i<=N;i++)printf("%d\n",answer[i]); }