fork download 
  1. #include<stdio.h>
  2. #include<vector>
  3.  
  4. using namespace std;
  5. long long mod = 1e9 + 7;
  6. vector<int>edge[121212];
  7. bool is_gone[121212];
  8. int C[121212];
  9. long long D[121212][4];
  10. void dfs(int w) {
  11. 	int i;
  12. 	is_gone[w] = 1;
  13. 	if (C[w] & 1)D[w][0] = 1;
  14. 	if (C[w] & 2)D[w][1] = 1;
  15. 	if (C[w] & 4)D[w][2] = 1;
  16. 	for (i = 0; i < edge[w].size(); i++) {
  17. 		if (is_gone[edge[w][i]])continue;
  18. 		dfs(edge[w][i]);
  19. 		D[w][0] *= (D[edge[w][i]][1] + D[edge[w][i]][2])%mod;
  20. 		D[w][1] *= (D[edge[w][i]][2] + D[edge[w][i]][0])%mod;
  21. 		D[w][2] *= (D[edge[w][i]][0] + D[edge[w][i]][1])%mod;
  22. 		D[w][0] %= mod;D[w][1] %= mod;D[w][2] %= mod;
  23. 	}
  24. }
  25. int main() {
  26. 	int n, k;
  27. 	int i, j;
  28. 	scanf("%d%d", &n, &k);
  29. 	for (i = 0; i < n - 1; i++) {
  30. 		int x, y;
  31. 		scanf("%d%d", &x, &y);
  32. 		edge[x].push_back(y);
  33. 		edge[y].push_back(x);
  34. 	}
  35. 	for (i = 1; i <= n; i++)C[i] = (1 << 3) - 1;
  36. 	for (i = 0; i < k; i++) {
  37. 		int x, y;
  38. 		scanf("%d%d", &x, &y);
  39. 		C[x] = (1<<(y-1));
  40. 	}
  41. 	dfs(1);
  42. 	printf("%lld", (D[1][0] + D[1][1] + D[1][2])%mod);
  43. 	return 0;
  44. }
Success #stdin #stdout 0s 5428KB
comments (?)
stdin 
4 1
1 2
1 3
1 4
4 3
stdout 
8
https://ideone.com/4ycXSf
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!