fork download 
  1. #include<iostream>
  2. #include<algorithm>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<vector>
  6. #include<set>
  7. #define REP(i,m) for(int i=0;i<m;++i)
  8. #define REPN(i,m,in) for(int i=in;i<m;++i)
  9. #define ALL(t) (t).begin(),(t).end()
  10. #define pb push_back
  11. #define mp make_pair
  12. #define fr first
  13. #define sc second
  14. #define dump(x)  cerr << #x << " = " << (x) << endl
  15. #define prl cerr<<"called:"<< __LINE__<<endl
  16. using namespace std;
  17. static const int INF =500000000; 
  18. template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;}
  19. typedef long long int lint;
  20. typedef pair<int,int> pi;
  21.  
  22. int n,m,q;
  23. vector<pi> g[100005];
  24. pi es[100005];
  25. int enable[100005];
  26. int event[200005];
  27.  
  28. int ans[100005];
  29.  
  30. int mark[100005];
  31. void fill(int v){
  32.     mark[v]=1;
  33. 	REP(i,g[v].size()){
  34. 		int to=g[v][i].fr,id=g[v][i].sc;
  35. 		if(!mark[to] && enable[id]) fill(to);
  36. 	}
  37. }
  38.  
  39. pi range[100005];
  40. int main(){
  41. 	scanf("%d%d%d",&n,&m,&q);
  42. 	REP(i,n-1){
  43. 		int a,b;scanf("%d%d",&a,&b);
  44. 		--a;--b;
  45. 		g[a].pb(mp(b,i));
  46. 		g[b].pb(mp(a,i));
  47. 		es[i]=mp(a,b);
  48. 	}
  49. 	REP(i,m) scanf("%d",&event[i]),--event[i];
  50. 	if(q==1){//for subtask 1
  51. 		int root;scanf("%d",&root);--root;
  52. 		REP(i,m) enable[event[i]]^=1;
  53. 		fill(root);
  54. 		for(int i=m-1;i>=0;--i){
  55. 			int e=event[i];
  56. 			if(enable[e]==0){
  57. 				if(mark[es[e].fr]^mark[es[e].sc]){
  58. 					if(mark[es[e].fr]) swap(es[e].fr,es[e].sc);
  59. 					fill(es[e].fr);
  60. 				}
  61. 			}
  62. 			enable[e]^=1;
  63. 		}
  64. 		int res=0;
  65. 		REP(i,n) if(mark[i]) ++res;
  66. 		printf("%d\n",res);
  67. 	}else{//this is solution for subtask 2
  68. 		set<int> divs;
  69. 		REP(i,n) divs.insert(i);
  70. 		REP(i,n) range[i]=mp(i,i+1);
  71.  
  72. 		REP(i,m){
  73. 			int e=event[i]+1;
  74.  
  75. 			set<int>::iterator it=divs.lower_bound(e);
  76. 			--it;
  77. 			if(enable[e]==0){
  78. 				divs.erase(e);
  79.  
  80. 				range[*it].sc=range[e].sc;
  81. 			}else{
  82. 				divs.insert(e);
  83. 				range[e]=range[*it];
  84. 			}
  85. 			enable[e]^=1;
  86. 		}
  87. 		REP(i,n){
  88. 			set<int>::iterator it=divs.lower_bound(i+1);
  89. 			--it;
  90. 			printf("%d\n",range[*it].sc-range[*it].fr);
  91. 		}
  92. 	}
  93.  
  94.  
  95.  
  96.  
  97.  
  98. 	return 0;
  99. }
  100.  
  101.  
  102.  
Success #stdin #stdout 0s 7544KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/eeGZxy
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!