/**
 *    author:  tourist
 *    created: 27.01.2020 06:45:41       
**/
#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  string s;
  cin >> s;
  vector<int> depth(n);
  vector<int> height(n);
  vector<int> pv(n);
  vector<int> sum(n);
  function<void(int, int)> Dfs = [&](int v, int pr) {
    height[v] = 0;
    sum[v] = (s[v] == '1');
    for (int u : g[v]) {
      if (u == pr) {
        continue;
      }
      depth[u] = depth[v] + 1;
      pv[u] = v;
      Dfs(u, v);
      sum[v] += sum[u];
      height[v] = max(height[v], height[u] + 1);
    }
  };
  depth[0] = 0;
  Dfs(0, -1);
  long long ans = 1;
  function<void(int, int)> Solve = [&](int v, int up) {
    vector<int> children;
    for (int u : g[v]) {
      if (u == pv[v]) {
        continue;
      }
      children.push_back(u);
    }
    int h1 = 0, h2 = 0;
    for (int u : children) {
      if (height[u] + 1 > h1) {
        h2 = h1;
        h1 = height[u] + 1;
      } else {
        if (height[u] + 1 > h2) {
          h2 = height[u] + 1;
        }
      }
    }
    for (int u : children) {
      if (height[u] + 1 == h1) {
        Solve(u, max(up, h2) + 1);
      } else {
        Solve(u, max(up, h1) + 1);
      }
    }
    if (up > h1) {
      h2 = h1;
      h1 = up;
    } else {
      if (up > h2) {
        h2 = up;
      }
    }
    if (s[v] == '1') {
      ans += h2;
    } else {
      int mn = h2;
      for (int u : children) {
        if (sum[u] > 0) {
          mn = min(mn, height[u] + 1);
        }
      }
      if (sum[v] < sum[0]) {
        mn = min(mn, up);
      }
      ans += h2 - mn;
    }
    bool ok = (s[v] == '1');
    if (h1 == up) {
      ok |= (sum[v] > 0);
    } else {
      for (int u : children) {
        if (h1 == height[u] + 1) {
          ok |= (sum[u] < sum[0]);
          break;
        }
      }
    }
    if (ok) {
      if (h1 > h2) {
        ans += 1;
      }
      if (h1 - 1 > h2) {
        ans += 1;
      }
    }
  };
  Solve(0, 0);
  cout << ans << '\n';
  return 0;
}

### Prompt

Generate a cpp solution to the following problem:

There is a tree with N vertices. The vertices are numbered 1 through N. For each 1 ≤ i ≤ N - 1, the i-th edge connects vertices a_i and b_i. The lengths of all the edges are 1.

Snuke likes some of the vertices. The information on his favorite vertices are given to you as a string s of length N. For each 1 ≤ i ≤ N, s_i is `1` if Snuke likes vertex i, and `0` if he does not like vertex i.

Initially, all the vertices are white. Snuke will perform the following operation exactly once:

* Select a vertex v that he likes, and a non-negative integer d. Then, paint all the vertices black whose distances from v are at most d.



Find the number of the possible combinations of colors of the vertices after the operation.

Constraints

* 2 ≤ N ≤ 2×10^5
* 1 ≤ a_i, b_i ≤ N
* The given graph is a tree.
* |s| = N
* s consists of `0` and `1`.
* s contains at least one occurrence of `1`.

Input

The input is given from Standard Input in the following format:


N
a_1 b_1
a_2 b_2
:
a_{N - 1} b_{N - 1}
s


Output

Print the number of the possible combinations of colors of the vertices after the operation.

Examples

Input

4
1 2
1 3
1 4
1100


Output

4


Input

5
1 2
1 3
1 4
4 5
11111


Output

11


Input

6
1 2
1 3
1 4
2 5
2 6
100011


Output

8

### Response

```cpp
/**
 *    author:  tourist
 *    created: 27.01.2020 06:45:41       
**/
#include <bits/stdc++.h>

using namespace std;

template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  cin >> n;
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int x, y;
    cin >> x >> y;
    --x; --y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  string s;
  cin >> s;
  vector<int> depth(n);
  vector<int> height(n);
  vector<int> pv(n);
  vector<int> sum(n);
  function<void(int, int)> Dfs = [&](int v, int pr) {
    height[v] = 0;
    sum[v] = (s[v] == '1');
    for (int u : g[v]) {
      if (u == pr) {
        continue;
      }
      depth[u] = depth[v] + 1;
      pv[u] = v;
      Dfs(u, v);
      sum[v] += sum[u];
      height[v] = max(height[v], height[u] + 1);
    }
  };
  depth[0] = 0;
  Dfs(0, -1);
  long long ans = 1;
  function<void(int, int)> Solve = [&](int v, int up) {
    vector<int> children;
    for (int u : g[v]) {
      if (u == pv[v]) {
        continue;
      }
      children.push_back(u);
    }
    int h1 = 0, h2 = 0;
    for (int u : children) {
      if (height[u] + 1 > h1) {
        h2 = h1;
        h1 = height[u] + 1;
      } else {
        if (height[u] + 1 > h2) {
          h2 = height[u] + 1;
        }
      }
    }
    for (int u : children) {
      if (height[u] + 1 == h1) {
        Solve(u, max(up, h2) + 1);
      } else {
        Solve(u, max(up, h1) + 1);
      }
    }
    if (up > h1) {
      h2 = h1;
      h1 = up;
    } else {
      if (up > h2) {
        h2 = up;
      }
    }
    if (s[v] == '1') {
      ans += h2;
    } else {
      int mn = h2;
      for (int u : children) {
        if (sum[u] > 0) {
          mn = min(mn, height[u] + 1);
        }
      }
      if (sum[v] < sum[0]) {
        mn = min(mn, up);
      }
      ans += h2 - mn;
    }
    bool ok = (s[v] == '1');
    if (h1 == up) {
      ok |= (sum[v] > 0);
    } else {
      for (int u : children) {
        if (h1 == height[u] + 1) {
          ok |= (sum[u] < sum[0]);
          break;
        }
      }
    }
    if (ok) {
      if (h1 > h2) {
        ans += 1;
      }
      if (h1 - 1 > h2) {
        ans += 1;
      }
    }
  };
  Solve(0, 0);
  cout << ans << '\n';
  return 0;
}

```