#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i) 
const int N = 200005, M = N << 1, inf = 1e9 + 7 ;
using namespace std ;

int e, n, ter[M], nxt[M], lnk[N], v[N], f[N][3], g[N][3] ;
char s[N] ;
ll ans = 0 ;

void add(int x, int y) {
	ter[++ e] = y, nxt[e] = lnk[x], lnk[x] = e ;
}

void dfs1(int p, int las) {
	f[p][0] = 0, f[p][1] = inf, g[p][0] = g[p][1] = inf ;
	if (v[p]) g[p][0] = 0 ;
	for (int i = lnk[p]; i; i = nxt[i]) if (ter[i] != las) {
		int v = ter[i] ;
		dfs1(v, p) ;
		if (f[v][0] + 1 > f[p][0]) f[p][1] = f[p][0], f[p][0] = f[v][0] + 1 ; else f[p][1] = max(f[p][1], f[v][0] + 1) ;
		if (g[v][0] + 1 < g[p][0]) g[p][1] = g[p][0], g[p][0] = g[v][0] + 1 ; else g[p][1] = min(g[p][1], g[v][0] + 1) ;
	}
}

void dfs2(int p, int u) {
	f[p][2] = 0, g[p][2] = inf ;
	if (u) {
		f[p][2] = max(f[p][2], f[u][2] + 1) ;
		if (f[p][0] + 1 == f[u][0]) f[p][2] = max(f[p][2], f[u][1] + 1) ; else
		  f[p][2] = max(f[p][2], f[u][0] + 1) ;
		g[p][2] = min(g[p][2], g[u][2] + 1) ;
		if (g[p][0] + 1 == g[u][0]) g[p][2] = min(g[p][2], g[u][1] + 1) ; else
		  g[p][2] = min(g[p][2], g[u][0] + 1) ;
	} 
	for (int i = lnk[p]; i; i = nxt[i]) if (ter[i] != u) dfs2(ter[i], p) ;
}

void dfs3(int p, int las) {
	int low = inf, high = f[p][0] + 1, mx = max(f[p][2], f[p][0]), cnt = (las > 0) ;
	if (las && g[p][2] < inf) low = min(low, min(f[p][2], f[p][0] + 2 * g[p][2])) ; 
	for (int i = lnk[p]; i; i = nxt[i]) if (ter[i] != las) {
		dfs3(ter[i], p) ;
		high = min(high, f[ter[i]][2]) ;
		++ cnt ;
		if (g[ter[i]][0] < inf) low = min(low, min(f[ter[i]][0] + 1, f[ter[i]][2] - 1 + (g[ter[i]][0] + 1) * 2)) ;
	}
	high = min(high, mx - 1) ;
	if (cnt == 1) {
		low = min(low, 2 * g[p][0]) ;
		low = min(low, 2 * g[p][2]) ;
		high = min(high, 1) ;
	}
	if (v[p]) low = 0 ;
//	cout << p << " " << low << " " << high <<endl ;
	ans += max(high - low + 1, 0) ;
}

int main() {
	scanf("%d", &n) ;
	int x, y ;
	rep(i, 1, n - 1) {
		scanf("%d%d", &x, &y) ;
		add(x, y), add(y, x) ;
	}
	scanf("%s", s + 1) ;
	rep(i, 1, n) v[i] = s[i] - '0' ;
	dfs1(1, 0), dfs2(1, 0), dfs3(1, 0) ;
	printf("%lld\n", ans + 1) ;
	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
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
typedef long long ll ;
#define rep(i, a, b) for (int i = a; i <= b; ++ i) 
const int N = 200005, M = N << 1, inf = 1e9 + 7 ;
using namespace std ;

int e, n, ter[M], nxt[M], lnk[N], v[N], f[N][3], g[N][3] ;
char s[N] ;
ll ans = 0 ;

void add(int x, int y) {
	ter[++ e] = y, nxt[e] = lnk[x], lnk[x] = e ;
}

void dfs1(int p, int las) {
	f[p][0] = 0, f[p][1] = inf, g[p][0] = g[p][1] = inf ;
	if (v[p]) g[p][0] = 0 ;
	for (int i = lnk[p]; i; i = nxt[i]) if (ter[i] != las) {
		int v = ter[i] ;
		dfs1(v, p) ;
		if (f[v][0] + 1 > f[p][0]) f[p][1] = f[p][0], f[p][0] = f[v][0] + 1 ; else f[p][1] = max(f[p][1], f[v][0] + 1) ;
		if (g[v][0] + 1 < g[p][0]) g[p][1] = g[p][0], g[p][0] = g[v][0] + 1 ; else g[p][1] = min(g[p][1], g[v][0] + 1) ;
	}
}

void dfs2(int p, int u) {
	f[p][2] = 0, g[p][2] = inf ;
	if (u) {
		f[p][2] = max(f[p][2], f[u][2] + 1) ;
		if (f[p][0] + 1 == f[u][0]) f[p][2] = max(f[p][2], f[u][1] + 1) ; else
		  f[p][2] = max(f[p][2], f[u][0] + 1) ;
		g[p][2] = min(g[p][2], g[u][2] + 1) ;
		if (g[p][0] + 1 == g[u][0]) g[p][2] = min(g[p][2], g[u][1] + 1) ; else
		  g[p][2] = min(g[p][2], g[u][0] + 1) ;
	} 
	for (int i = lnk[p]; i; i = nxt[i]) if (ter[i] != u) dfs2(ter[i], p) ;
}

void dfs3(int p, int las) {
	int low = inf, high = f[p][0] + 1, mx = max(f[p][2], f[p][0]), cnt = (las > 0) ;
	if (las && g[p][2] < inf) low = min(low, min(f[p][2], f[p][0] + 2 * g[p][2])) ; 
	for (int i = lnk[p]; i; i = nxt[i]) if (ter[i] != las) {
		dfs3(ter[i], p) ;
		high = min(high, f[ter[i]][2]) ;
		++ cnt ;
		if (g[ter[i]][0] < inf) low = min(low, min(f[ter[i]][0] + 1, f[ter[i]][2] - 1 + (g[ter[i]][0] + 1) * 2)) ;
	}
	high = min(high, mx - 1) ;
	if (cnt == 1) {
		low = min(low, 2 * g[p][0]) ;
		low = min(low, 2 * g[p][2]) ;
		high = min(high, 1) ;
	}
	if (v[p]) low = 0 ;
//	cout << p << " " << low << " " << high <<endl ;
	ans += max(high - low + 1, 0) ;
}

int main() {
	scanf("%d", &n) ;
	int x, y ;
	rep(i, 1, n - 1) {
		scanf("%d%d", &x, &y) ;
		add(x, y), add(y, x) ;
	}
	scanf("%s", s + 1) ;
	rep(i, 1, n) v[i] = s[i] - '0' ;
	dfs1(1, 0), dfs2(1, 0), dfs3(1, 0) ;
	printf("%lld\n", ans + 1) ;
	return 0 ; 
}
```