fork download 
  1. #define _CRT_SECURE_NO_WARNINGS
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5.  
  6. typedef struct adjNode {
  7. 	int v;
  8. 	struct adjNode *next;
  9. }adjNode;
  10.  
  11. adjNode **Adj;
  12.  
  13. typedef struct vInfo {
  14. 	int visited;
  15. 	int parent;
  16. 	int set;
  17. }vInfo;
  18.  
  19. vInfo *Info;
  20. int n;
  21. int visited = 0;
  22. long long setN[2] = { 1, 0 };
  23.  
  24. void dfs(int u);
  25. void insertEdge(int v1, int v2);
  26. void initInfo();
  27.  
  28. int main(void) {
  29. 	scanf("%d", &n);
  30. 	Adj = calloc((n + 1), sizeof(struct adjNode *));
  31. 	Info = malloc((n + 1) * sizeof(struct vInfo));
  32.  
  33. 	initInfo();
  34. 	int v1, v2;
  35. 	for (size_t i = 1; i < n; i++)
  36. 	{
  37. 		scanf("%d %d", &v1, &v2);
  38. 		insertEdge(v1, v2);
  39. 	}
  40.  
  41. 	dfs(1);
  42. 	finish();
  43. }
  44.  
  45. void dfs(int u) {
  46. 	Info[u].visited = 1;
  47. 	visited++;
  48.  
  49. 	for (adjNode *vAdj = Adj[u]; vAdj != NULL; vAdj = vAdj->next)
  50. 	{
  51. 		if (!Info[vAdj->v].visited)
  52. 		{
  53. 			Info[vAdj->v].parent = u;
  54. 			Info[vAdj->v].set = 1 - Info[u].set;
  55. 			setN[Info[vAdj->v].set]++;
  56. 			dfs(vAdj->v);
  57. 			if (visited == n)
  58. 			{
  59. 				finish();
  60. 			}
  61. 		}
  62. 	}
  63. }
  64.  
  65. void insertEdge(int v1, int v2) {
  66. 	adjNode *v1v2 = malloc(sizeof(struct adjNode));
  67. 	v1v2->next = NULL;
  68. 	v1v2->v = v2;
  69. 	adjNode *v2v1 = malloc(sizeof(struct adjNode));
  70. 	v2v1->next = NULL;
  71. 	v2v1->v = v1;
  72.  
  73. 	adjNode *iter;
  74. 	if (Adj[v1] == NULL)
  75. 		Adj[v1] = v1v2;
  76. 	else {
  77. 		for (iter = Adj[v1]; iter->next != NULL; iter = iter->next);
  78. 		iter->next = v1v2;
  79. 	}
  80.  
  81. 	if (Adj[v2] == NULL)
  82. 		Adj[v2] = v2v1;
  83. 	else {
  84. 		for (iter = Adj[v2]; iter->next != NULL; iter = iter->next);
  85. 		iter->next = v2v1;
  86. 	}
  87. }
  88.  
  89. void initInfo() {
  90. 	for (size_t i = 1; i <= n; i++)
  91. 	{
  92. 		Info[i].visited = 0;
  93. 		Info[i].parent = -1;
  94. 		Info[i].set = 0;
  95. 	}
  96. }
  97.  
  98. void finish() {
  99. 	printf("%lld", setN[0] * setN[1] - (n - 1));
  100. 	exit(0);
  101. }
Success #stdin #stdout 0s 4172KB
comments (?)
stdin 
10
3 8
6 2
9 7
10 1
3 5
1 3
6 7
5 4
3 6
stdout 
16
https://ideone.com/cFfNPN
language:
C (gcc 8.3)
created:
6 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!