fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define f first
  3. #define s second
  4. #define pii pair<int,int>
  5. using namespace std;
  6. const int N = 4e6 + 5;
  7. int t, tmin[N],tmout[N],mx[N],mn[N],timer,ans,n,f[N];
  8. pii dp[N];
  9. vector<int> V[N];
  10. void dfs1(int u,int p) {
  11. 	tmin[u] = ++timer;
  12. 	if(!mn[f[u]]) mn[f[u]] = timer;
  13. 	mx[f[u]] = timer;
  14. 	for(int i = 0; i < V[u].size(); i++) {
  15. 		if(V[u][i] == p) continue;
  16. 		dfs1(V[u][i],u);
  17. 	}
  18. 	tmout[u] = timer;
  19. }
  20. void dfs2(int u,int p) {
  21. 	dp[u].f = mn[f[u]];
  22. 	dp[u].s = mx[f[u]];
  23. 	for(int i = 0; i < V[u].size(); i++) {
  24. 		if(V[u][i] == p) continue;
  25. 		dfs2(V[u][i],u);
  26. 		dp[u].f = min(dp[V[u][i]].f,dp[u].f);
  27. 		dp[u].s = max(dp[V[u][i]].s,dp[u].s);
  28. 	}
  29. 	if(dp[u].f < tmin[u] || dp[u].s > tmout[u] || u == 1) return;
  30. 	ans++;
  31. }
  32. signed main(){
  33. 	//freopen("chainblock_input.txt","r",stdin);
  34.    	//freopen("ans.txt","w",stdout);
  35. 	scanf("%d",&t);
  36. 	int T = 0;
  37. 	while(t--){
  38. 	   scanf("%d",&n);
  39. 	   for(int i = 1; i <= n; i++) V[i].clear(), mn[i] = 0;
  40. 	   timer = 0; ans = 0;
  41. 	   for(int i = 1; i < n; i++){
  42. 	   		int u,v;
  43. 	   		scanf("%d",&u); 
  44. 			scanf("%d",&v);
  45. 	   		V[u].push_back(v); V[v].push_back(u);
  46. 	   }
  47. 	   for(int i = 1; i <= n; i++) scanf("%d",&f[i]);
  48. 	   dfs1(1,0);
  49. 	   dfs2(1,0);
  50. 	   cout << "Case #"<<++T<<": "<<ans<<endl;
  51. 	}
  52.  }
Success #stdin #stdout 0.02s 98076KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/I8Uyuh
language:
C++14 (gcc 8.3)
created:
2 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!