#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long i64;
const int MAX_N = 200005;

class Edge {
public:
  int nxt, to;
} e[MAX_N << 1];

int head[MAX_N], cnt;
void addedge(int u, int v) {
  e[++cnt] = (Edge){head[u], v}, head[u] = cnt;
  e[++cnt] = (Edge){head[v], u}, head[v] = cnt;
}

int N;
char S[MAX_N];
int mx[MAX_N], smx[MAX_N], num[MAX_N], low[MAX_N];

void update(int x, int v) {
  if (mx[x] <= v) smx[x] = mx[x], mx[x] = v;
  else if (smx[x] < v) smx[x] = v;
}

void dfs1(int u, int v) {
  mx[u] = 0, num[u] = S[u], low[u] = N;
  for (int i = head[u]; i; i = e[i].nxt) 
    if (e[i].to != v) {
      dfs1(e[i].to, u);
      if (num[e[i].to]) low[u] = min(low[u], mx[e[i].to] + 1);
      num[u] += num[e[i].to];
      update(u, mx[e[i].to] + 1);
    }
}

void dfs2(int u, int v) {
  for (int i = head[u]; i; i = e[i].nxt)
    if (e[i].to != v) {
      int d;
      if (mx[u] == mx[e[i].to] + 1) {
	d = smx[u] + 1;
      } else {
	d = mx[u] + 1;
      }
      update(e[i].to, d);
      if (num[u] - num[e[i].to] > 0) low[e[i].to] = min(low[e[i].to], d);
      num[e[i].to] = num[u];
      dfs2(e[i].to, u);
    }
}

int main() {
  scanf("%d", &N);
  for (int i = 1, u, v; i < N; ++i) {
    scanf("%d%d", &u, &v);
    addedge(u, v);
  }
  
  scanf("%s", S + 1);
  for (int i = 1; i <= N; ++i) S[i] = S[i] - '0';
  
  dfs1(1, 0);
  dfs2(1, 0);

  i64 res = 0;
  for (int i = 1; i <= N; ++i) {
    int h = min(mx[i], smx[i] + 2);
    int l = S[i] ? 0 : low[i];

    res += max(0, h - l);
  }
  
  printf("%lld\n", res + 1);
  return 0;
}

### Prompt

Please formulate 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
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

typedef long long i64;
const int MAX_N = 200005;

class Edge {
public:
  int nxt, to;
} e[MAX_N << 1];

int head[MAX_N], cnt;
void addedge(int u, int v) {
  e[++cnt] = (Edge){head[u], v}, head[u] = cnt;
  e[++cnt] = (Edge){head[v], u}, head[v] = cnt;
}

int N;
char S[MAX_N];
int mx[MAX_N], smx[MAX_N], num[MAX_N], low[MAX_N];

void update(int x, int v) {
  if (mx[x] <= v) smx[x] = mx[x], mx[x] = v;
  else if (smx[x] < v) smx[x] = v;
}

void dfs1(int u, int v) {
  mx[u] = 0, num[u] = S[u], low[u] = N;
  for (int i = head[u]; i; i = e[i].nxt) 
    if (e[i].to != v) {
      dfs1(e[i].to, u);
      if (num[e[i].to]) low[u] = min(low[u], mx[e[i].to] + 1);
      num[u] += num[e[i].to];
      update(u, mx[e[i].to] + 1);
    }
}

void dfs2(int u, int v) {
  for (int i = head[u]; i; i = e[i].nxt)
    if (e[i].to != v) {
      int d;
      if (mx[u] == mx[e[i].to] + 1) {
	d = smx[u] + 1;
      } else {
	d = mx[u] + 1;
      }
      update(e[i].to, d);
      if (num[u] - num[e[i].to] > 0) low[e[i].to] = min(low[e[i].to], d);
      num[e[i].to] = num[u];
      dfs2(e[i].to, u);
    }
}

int main() {
  scanf("%d", &N);
  for (int i = 1, u, v; i < N; ++i) {
    scanf("%d%d", &u, &v);
    addedge(u, v);
  }
  
  scanf("%s", S + 1);
  for (int i = 1; i <= N; ++i) S[i] = S[i] - '0';
  
  dfs1(1, 0);
  dfs2(1, 0);

  i64 res = 0;
  for (int i = 1; i <= N; ++i) {
    int h = min(mx[i], smx[i] + 2);
    int l = S[i] ? 0 : low[i];

    res += max(0, h - l);
  }
  
  printf("%lld\n", res + 1);
  return 0;
}

```