fork download
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<long long> A, AO, P, PE, PO;
  5. vector<vector<int>> E;
  6.  
  7. void dfs(int u, int p)
  8. {
  9. for (int v: E[u]) {
  10. if (v == p) {
  11. continue;
  12. }
  13.  
  14. dfs(v, u);
  15.  
  16. A[u] += A[v];
  17. AO[u] += AO[v];
  18.  
  19. A[u] += P[v] + PE[v] + PO[v] + 1;
  20. AO[u] += PE[v] + 1;
  21.  
  22. A[u] += P[u] * (PE[v] + PO[v] + 1) + (P[v] + PE[v] + PO[v] + 1) * (PE[u] + PO[u]);
  23. AO[u] += PO[u] * PO[v] + PE[u] * (PE[v] + 1);
  24.  
  25. P[u] += P[v] + PE[v] + PO[v] + 1;
  26. PE[u] += PO[v];
  27. PO[u] += PE[v] + 1;
  28. }
  29. }
  30.  
  31. int main()
  32. {
  33. int n;
  34. cin >> n;
  35. E.assign(1 + n, vector<int>());
  36. for (int i = 1; i < n; ++i) {
  37. int u, v;
  38. cin >> u >> v;
  39. E[u].push_back(v);
  40. E[v].push_back(u);
  41. }
  42. A.assign(1 + n, 0);
  43. AO.assign(1 + n, 0);
  44. P.assign(1 + n, 0);
  45. PE.assign(1 + n, 0);
  46. PO.assign(1 + n, 0);
  47. dfs(1, -1);
  48. cout << (A[1] - AO[1]) / 2 + AO[1] << endl;
  49. return 0;
  50. }
Success #stdin #stdout 0s 4432KB
stdin
10
1 2
1 3
1 4
2 5
3 6
3 7
4 8
4 9
4 10
stdout
68