#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define PR pair
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define REP(i, x, y)   for(int i = (int)(x); i <= (int)(y); i++)
#define FOR(i, x, y)   for(int i = (int)(x); i <  (int)(y); i++)
#define PER(i ,x, y)  for(int i = (int)(x); i >= (int)(y); i--)
#define CH	         ch = getchar()
#define Exit(...)    printf(__VA_ARGS__), exit(0)
#define dln()        fprintf(stderr,"\n")
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef double	  db;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI > VII;
typedef PR<int,int> PII;
typedef vector<PII> VPI;
const	int inf=2e9;
const	LL Inf=1e10;
const	int P=1e9+7;
const	int N=200005;

inline LL IN(){
	LL x = 0;
	int ch = 0, f = 0;
	for (CH; ch != -1 && (ch < 48 || ch > 57); CH) f = (ch == '-');
	for (; ch >= 48 && ch <= 57; CH) x = (x << 1) + (x << 3) + ch - '0';
	return f ? (-x) : x;
}
template<typename T> inline int chkmin(T &a, const T &b){if(b < a) return a = b, 1; return 0;}
template<typename T> inline int chkmax(T &a, const T &b){if(b > a) return a = b, 1; return 0;}

void renew(int &x, const int &y){
	x += y;
	if(x >= P) x -= P;
	if(x <  0) x += P;
}

int Pow(int x, int y, int p){
	int a = 1;
	for (; y; y >>= 1, x = (LL)x * x %p) if(y & 1) a=(LL)a * x%p;
	return a;
}

int n;
int mxd[N], sed[N], mad[N], gg[N], hev[N];
struct edge{
	int v, pre;
}e[N << 1]; int dex, adj[N];
int fa[N];

void dfs(int x){
	for(int i = adj[x]; i; i = e[i].pre){
		int v = e[i].v;
		if(v == fa[x]) continue;
		fa[v] = x;
		dfs(v);
		if(mxd[v] + 1 > mxd[x]){
			sed[x] = mxd[x];
			hev[x] = v;
			mxd[x] = mxd[v] + 1;
		}else
		if(mxd[v] + 1 > sed[x]){
			sed[x] = mxd[v] + 1;
		}
	}
}

void dp(int x){
	for(int i = adj[x]; i; i = e[i].pre){
		int v = e[i].v;
		if(v == fa[x]) continue;
		if(v == hev[x]){
			gg[v] = max(gg[x], sed[x]) + 1;
		}else{
			gg[v] = max(gg[x], mxd[x]) + 1;
		}
		dp(v);
	}
}

int hg[N], lo[N];
LL ans = 1;
char s[N];

void work(int x, int par){
	mad[x] = 0;
	if(s[x] == '1') lo[x] = 0; else lo[x] = 1 << 30;
	for(int i = adj[x]; i; i = e[i].pre){
		int v = e[i].v;
		if(v == par) continue;
		work(v, x);
		mad[x] = max(mad[x], mad[v] + 1);
		lo[x] = min(lo[x], lo[v] - 1);
	}
	hg[x] = min(mad[x] + 1, mxd[x] - 1);
	ans += max(0, hg[x] - lo[x] + 1);
	lo[x] = max(lo[x], hg[x] + 1);
	if(lo[x] == mxd[x]) lo[x] = 1 << 30;
}

int main(){
	scanf("%d", &n);
	REP(i, 1, n - 1){
		int x, y;
		scanf("%d%d", &x, &y);
		e[++dex] = (edge){y, adj[x]}; adj[x] = dex;
		e[++dex] = (edge){x, adj[y]}; adj[y] = dex;
	}
	dfs(1);
	dp(1);
	REP(i, 1, n) mxd[i] = max(mxd[i], gg[i]);
	int rt = min_element(mxd + 1, mxd + n + 1) - mxd;
	scanf("%s", s + 1);
	work(rt, 0);
	cout << ans << endl;
	return 0;
}
### Prompt

Construct a cpp code solution to the problem outlined:

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 <set>
#include <map>
#include <cmath>
#include <ctime>
#include <bitset>
#include <string>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#define PR pair
#define fi first
#define se second
#define mk make_pair
#define pb push_back
#define REP(i, x, y)   for(int i = (int)(x); i <= (int)(y); i++)
#define FOR(i, x, y)   for(int i = (int)(x); i <  (int)(y); i++)
#define PER(i ,x, y)  for(int i = (int)(x); i >= (int)(y); i--)
#define CH	         ch = getchar()
#define Exit(...)    printf(__VA_ARGS__), exit(0)
#define dln()        fprintf(stderr,"\n")
#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef double	  db;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI > VII;
typedef PR<int,int> PII;
typedef vector<PII> VPI;
const	int inf=2e9;
const	LL Inf=1e10;
const	int P=1e9+7;
const	int N=200005;

inline LL IN(){
	LL x = 0;
	int ch = 0, f = 0;
	for (CH; ch != -1 && (ch < 48 || ch > 57); CH) f = (ch == '-');
	for (; ch >= 48 && ch <= 57; CH) x = (x << 1) + (x << 3) + ch - '0';
	return f ? (-x) : x;
}
template<typename T> inline int chkmin(T &a, const T &b){if(b < a) return a = b, 1; return 0;}
template<typename T> inline int chkmax(T &a, const T &b){if(b > a) return a = b, 1; return 0;}

void renew(int &x, const int &y){
	x += y;
	if(x >= P) x -= P;
	if(x <  0) x += P;
}

int Pow(int x, int y, int p){
	int a = 1;
	for (; y; y >>= 1, x = (LL)x * x %p) if(y & 1) a=(LL)a * x%p;
	return a;
}

int n;
int mxd[N], sed[N], mad[N], gg[N], hev[N];
struct edge{
	int v, pre;
}e[N << 1]; int dex, adj[N];
int fa[N];

void dfs(int x){
	for(int i = adj[x]; i; i = e[i].pre){
		int v = e[i].v;
		if(v == fa[x]) continue;
		fa[v] = x;
		dfs(v);
		if(mxd[v] + 1 > mxd[x]){
			sed[x] = mxd[x];
			hev[x] = v;
			mxd[x] = mxd[v] + 1;
		}else
		if(mxd[v] + 1 > sed[x]){
			sed[x] = mxd[v] + 1;
		}
	}
}

void dp(int x){
	for(int i = adj[x]; i; i = e[i].pre){
		int v = e[i].v;
		if(v == fa[x]) continue;
		if(v == hev[x]){
			gg[v] = max(gg[x], sed[x]) + 1;
		}else{
			gg[v] = max(gg[x], mxd[x]) + 1;
		}
		dp(v);
	}
}

int hg[N], lo[N];
LL ans = 1;
char s[N];

void work(int x, int par){
	mad[x] = 0;
	if(s[x] == '1') lo[x] = 0; else lo[x] = 1 << 30;
	for(int i = adj[x]; i; i = e[i].pre){
		int v = e[i].v;
		if(v == par) continue;
		work(v, x);
		mad[x] = max(mad[x], mad[v] + 1);
		lo[x] = min(lo[x], lo[v] - 1);
	}
	hg[x] = min(mad[x] + 1, mxd[x] - 1);
	ans += max(0, hg[x] - lo[x] + 1);
	lo[x] = max(lo[x], hg[x] + 1);
	if(lo[x] == mxd[x]) lo[x] = 1 << 30;
}

int main(){
	scanf("%d", &n);
	REP(i, 1, n - 1){
		int x, y;
		scanf("%d%d", &x, &y);
		e[++dex] = (edge){y, adj[x]}; adj[x] = dex;
		e[++dex] = (edge){x, adj[y]}; adj[y] = dex;
	}
	dfs(1);
	dp(1);
	REP(i, 1, n) mxd[i] = max(mxd[i], gg[i]);
	int rt = min_element(mxd + 1, mxd + n + 1) - mxd;
	scanf("%s", s + 1);
	work(rt, 0);
	cout << ans << endl;
	return 0;
}
```