func_code_string: #include <bits/stdc++.h>   using namespace std;   template <typename T, typename U>   inline void smin(T &a, const U &b) {     if (a > b) a = b;   }   template <typename T, typename U>   inline void smax(T &a, const U &b) {     if (a < b) a = b;   }   template <class T>   inline void gn(T &first) {     char c, sg = 0;     while (c = getchar(), (c >  9  || c <  0 ) && c !=  - )       ;     for ((c ==  -  ? sg = 1, c = getchar() : 0), first = 0; c >=  0  && c <=  9 ;          c = getchar())       first = (first << 1) + (first << 3) + c -  0 ;     if (sg) first = -first;   }   template <class T1, class T2>   inline void gn(T1 &x1, T2 &x2) {     gn(x1), gn(x2);   }   int power(int a, int b, int m, int ans = 1) {     for (; b; b >>= 1, a = 1LL * a * a % m)       if (b & 1) ans = 1LL * ans * a % m;     return ans;   }   vector<int> adj[500500];   int can0[500500], can1[500500], dp0[500500], dp1[500500];   int dp[4];   int n, sz[500500];   void dfs(int u, int f = 0) {     sz[u] = 1;     for (int v : adj[u])       if (v != f) dfs(v, u), sz[u] += sz[v];     can0[u] = 1;     dp[0] = 1, dp[1] = 0;     for (int v : adj[u]) {       if (v == f) continue;       can0[u] &= can1[v];       int t[2] = {dp[0], dp[1]};       dp[0] = t[0] * can1[v];       dp[1] = t[0] * can0[v] + t[1] * can1[v];     }     can1[u] = dp[1];     dp[0] = 1, dp[1] = 0;     for (int v : adj[u]) {       if (v == f) continue;       int t[2] = {dp[0], dp[1]};       dp[0] = t[0] * can1[v];       dp[1] = t[1] * can1[v] + t[0] * dp1[v];     }     dp0[u] = dp[1];     dp1[u] = can0[u];     dp[0] = 1, dp[1] = 0;     for (int v : adj[u]) {       if (v == f) continue;       int t[2] = {dp[0], dp[1]};       dp[0] = t[0] * can1[v];       dp[1] = t[1] * can1[v] + t[0] * dp0[v];     }     dp1[u] += dp[1];     dp[0] = 1, dp[1] = dp[2] = dp[3] = 0;     for (int v : adj[u]) {       if (v == f) continue;       int t[4] = {dp[0], dp[1], dp[2], dp[3]};       dp[0] = t[0] * can1[v];       dp[1] = t[0] * can0[v] + t[1] * can1[v];       dp[2] = t[0] * dp1[v] + t[2] * can1[v];       dp[3] = t[1] * dp1[v] + t[2] * can0[v] + t[3] * can1[v];     }     dp1[u] += dp[3];   }   long long ans;   int c0[500500], c1[500500], d0[500500], d1[500500];   int R[500500], Rdp[500500][4];   void redfs(int u, int f = 0) {     if (f) {       if (can1[u] && c1[u])         ans += (long long)sz[u] * (n - sz[u]);       else         ans += (long long)dp1[u] * d1[u];     }     R[adj[u].size()] = 1;     Rdp[adj[u].size()][0] = 1;     Rdp[adj[u].size()][1] = 0;     for (int i = adj[u].size(); i--;) {       int v = adj[u][i];       R[i] = R[i + 1] & (v == f ? c1[u] : can1[v]);       Rdp[i][0] = Rdp[i + 1][0] * (v == f ? c1[u] : can1[v]);       Rdp[i][1] = Rdp[i + 1][0] * (v == f ? c0[u] : can0[v]) +                   Rdp[i + 1][1] * (v == f ? c1[u] : can1[v]);     }     int cur = 1;     dp[0] = 1, dp[1] = 0;     for (int i = 0; i < adj[u].size(); i++) {       int v = adj[u][i];       if (v != f) {         c0[v] = cur & R[i + 1];         c1[v] = dp[0] & Rdp[i + 1][1] | dp[1] & Rdp[i + 1][0];       }       int t[2] = {dp[0], dp[1]};       cur &= (v == f ? c1[u] : can1[v]);       dp[0] = t[0] * (v == f ? c1[u] : can1[v]);       dp[1] =           t[0] * (v == f ? c0[u] : can0[v]) + t[1] * (v == f ? c1[u] : can1[v]);     }     Rdp[adj[u].size()][0] = 1;     Rdp[adj[u].size()][1] = 0;     for (int i = adj[u].size(); i--;) {       int v = adj[u][i];       Rdp[i][0] = Rdp[i + 1][0] * (v == f ? c1[u] : can1[v]);       Rdp[i][1] = Rdp[i + 1][0] * (v == f ? d1[u] : dp1[v]) +                   Rdp[i + 1][1] * (v == f ? c1[u] : can1[v]);     }     dp[0] = 1, dp[1] = 0;     for (int i = 0; i < adj[u].size(); i++) {       int v = adj[u][i];       if (v != f) d0[v] = dp[0] * Rdp[i + 1][1] + dp[1] * Rdp[i + 1][0];       int t[2] = {dp[0], dp[1]};       dp[0] = t[0] * (v == f ? c1[u] : can1[v]);       dp[1] =           t[1] * (v == f ? c1[u] : can1[v]) + t[0] * (v == f ? d1[u] : dp1[v]);     }     for (int v : adj[u])       if (v != f) d1[v] = c0[v];     Rdp[adj[u].size()][0] = 1;     Rdp[adj[u].size()][1] = 0;     for (int i = adj[u].size(); i--;) {       int v = adj[u][i];       Rdp[i][0] = Rdp[i + 1][0] * (v == f ? c1[u] : can1[v]);       Rdp[i][1] = Rdp[i + 1][0] * (v == f ? d0[u] : dp0[v]) +                   Rdp[i + 1][1] * (v == f ? c1[u] : can1[v]);     }     dp[0] = 1, dp[1] = 0;     for (int i = 0; i < adj[u].size(); i++) {       int v = adj[u][i];       if (v != f) d1[v] += dp[0] * Rdp[i + 1][1] + dp[1] * Rdp[i + 1][0];       int t[2] = {dp[0], dp[1]};       dp[0] = t[0] * (v == f ? c1[u] : can1[v]);       dp[1] =           t[1] * (v == f ? c1[u] : can1[v]) + t[0] * (v == f ? d0[u] : dp0[v]);     }     Rdp[adj[u].size()][0] = 1;     Rdp[adj[u].size()][1] = 0;     Rdp[adj[u].size()][2] = 0;     Rdp[adj[u].size()][3] = 0;     for (int i = adj[u].size(); i--;) {       int v = adj[u][i];       Rdp[i][0] = Rdp[i + 1][0] * (v == f ? c1[u] : can1[v]);       Rdp[i][1] = Rdp[i + 1][0] * (v == f ? c0[u] : can0[v]) +                   Rdp[i + 1][1] * (v == f ? c1[u] : can1[v]);       Rdp[i][2] = Rdp[i + 1][0] * (v == f ? d1[u] : dp1[v]) +                   Rdp[i + 1][2] * (v == f ? c1[u] : can1[v]);       Rdp[i][3] = Rdp[i + 1][1] * (v == f ? d1[u] : dp1[v]) +                   Rdp[i + 1][2] * (v == f ? c0[u] : can0[v]) +                   Rdp[i + 1][3] * (v == f ? c1[u] : can1[v]);     }     dp[0] = 1, dp[1] = dp[2] = dp[3] = 0;     for (int i = 0; i < adj[u].size(); i++) {       int v = adj[u][i];       if (v != f)         d1[v] += dp[0] * Rdp[i + 1][3] + dp[1] * Rdp[i + 1][2] +                  dp[2] * Rdp[i + 1][1] + dp[3] * Rdp[i + 1][0];       int t[4] = {dp[0], dp[1], dp[2], dp[3]};       dp[0] = t[0] * (v == f ? c1[u] : can1[v]);       dp[1] =           t[0] * (v == f ? c0[u] : can0[v]) + t[1] * (v == f ? c1[u] : can1[v]);       dp[2] =           t[0] * (v == f ? d1[u] : dp1[v]) + t[2] * (v == f ? c1[u] : can1[v]);       dp[3] = t[1] * (v == f ? d1[u] : dp1[v]) +               t[2] * (v == f ? c0[u] : can0[v]) +               t[3] * (v == f ? c1[u] : can1[v]);     }     for (int v : adj[u])       if (v != f) redfs(v, u);   }   int main() {     cin >> n;     for (int i = 1; i < n; i++) {       int u, v;       gn(u, v);       adj[u].push_back(v);       adj[v].push_back(u);     }     dfs(1);     redfs(1);     cout << ans << endl;     return 0;   }   