#include <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int) a.size()
#define ALL(a) a.begin(),a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const LL INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 200200;

struct edge
{
	int x, y;

	int depth;
	int any;

	edge()
	{
		x = y = -1;
		depth = 0;
		any = 0;
	}
};

vector<edge> E;
VI g[MAX];
VI I[MAX];
VI L[MAX];
VI R[MAX];
VI L2[MAX];
VI R2[MAX];
int D[MAX];
int U[MAX];
int ANY[MAX];
char S[MAX];

int dfs1(int x, int p)
{
	int res = 0;
	ANY[x] = S[x] - '0';
	FOR (i, 0, SZ(g[x]))
	{
		int e = g[x][i];
		int to = E[e].y;
		if (to == p) continue;

		E[e].depth = dfs1(to, x);
		res = max(res, E[e].depth);

		if (ANY[to])
		{
			ANY[x] = 1;
			E[e].any = true;
		}
	}
	return res + 1;
}

void dfs2(int x, int p, int ind)
{
	if (ind != -1)
	{
		int r = I[x][ind];

		int mx = 0;
		int mx2 = 0;
		if (r)
		{
			mx = max(mx, L[p][r - 1]);
			mx2 = max(mx2, L2[p][r - 1]);
		}
		if (r < SZ(g[p]) - 1)
		{
			mx = max(mx, R[p][r + 1]);
			mx2 = max(mx2, R2[p][r + 1]);
		}

		mx++;

		int e = g[x][ind];
		mx2 = max(mx2, S[E[e].y] - '0');

		E[e].depth = mx;
		E[e].any = mx2;
	}

	L[x].resize(SZ(g[x]));
	R[x].resize(SZ(g[x]));

	L2[x].resize(SZ(g[x]));
	R2[x].resize(SZ(g[x]));

	int mx = 0;
	int mx2 = 0;

	U[x] = INF;

	FOR (i, 0, SZ(g[x]))
	{
		int e = g[x][i];
		int val = E[e].depth;

		L[x][i] = R[x][i] = val;
		L2[x][i] = R2[x][i] = E[e].any;

		if (E[e].any)
		{
			U[x] = min(U[x], E[e].depth);
		}

		if (val > mx)
		{
			mx2 = mx;
			mx = val;
		}
		else
		{
			if (val > mx2)
			{
				mx2 = val;
			}
		}
	}

	D[x] = min(mx - 1, mx2 + 1);

	FOR (i, 1, SZ(g[x]))
	{
		L[x][i] = max(L[x][i], L[x][i-1]);
		L2[x][i] = max(L2[x][i], L2[x][i-1]);
	}

	RFOR(i, SZ(g[x]) - 1, 0)
	{
		R[x][i] = max(R[x][i], R[x][i+1]);
		R2[x][i] = max(R2[x][i], R2[x][i+1]);
	}



	FOR (i,0 , SZ(g[x]))
	{
		int e = g[x][i];
		int to = E[e].y;

		if (to == p) continue;
		dfs2(to, x, I[x][i]);
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);

	int n;
	scanf("%d", &n);
	FOR (i, 0, n-1)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		x--;
		y--;

		I[x].PB(SZ(g[y]));
		I[y].PB(SZ(g[x]));

		edge e;
		e.x = x; e.y = y;
		g[x].PB(SZ(E));
		E.PB(e);

		e.x = y; e.y = x;
		g[y].PB(SZ(E));
		E.PB(e);
	}

	scanf("%s", S);

	dfs1(0, -1);
	dfs2(0, -1, -1);

	LL res = 0;
	FOR (i, 0, n)
	{
		if (S[i] == '1') res += D[i] + 1;
		else
		{
			if (U[i] <= D[i])
			{
				res += D[i] - U[i] + 1;
			}
		}
	}
	res++;
	cout<<res<<endl;

	/*FOR (i, 0, n)
	{
		cout<<i<<' '<<D[i]<<' '<<U[i]<<endl;
	}
	cout<<endl;

	FOR (i, 0, SZ(E))
	{
		cout<<E[i].x<<' '<<E[i].y<<' '<<E[i].depth<<' '<<E[i].any<<endl;
	}*/



}

### 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 <bits/stdc++.h>
using namespace std;

#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,b,a) for(int i = (b) - 1; i >= (a); i--)
#define ITER(it, a) for(typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int) a.size()
#define ALL(a) a.begin(),a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const LL INF = 1000 * 1000 * 1000 + 7;
const LL LINF = INF * (LL)INF;

const int MAX = 200200;

struct edge
{
	int x, y;

	int depth;
	int any;

	edge()
	{
		x = y = -1;
		depth = 0;
		any = 0;
	}
};

vector<edge> E;
VI g[MAX];
VI I[MAX];
VI L[MAX];
VI R[MAX];
VI L2[MAX];
VI R2[MAX];
int D[MAX];
int U[MAX];
int ANY[MAX];
char S[MAX];

int dfs1(int x, int p)
{
	int res = 0;
	ANY[x] = S[x] - '0';
	FOR (i, 0, SZ(g[x]))
	{
		int e = g[x][i];
		int to = E[e].y;
		if (to == p) continue;

		E[e].depth = dfs1(to, x);
		res = max(res, E[e].depth);

		if (ANY[to])
		{
			ANY[x] = 1;
			E[e].any = true;
		}
	}
	return res + 1;
}

void dfs2(int x, int p, int ind)
{
	if (ind != -1)
	{
		int r = I[x][ind];

		int mx = 0;
		int mx2 = 0;
		if (r)
		{
			mx = max(mx, L[p][r - 1]);
			mx2 = max(mx2, L2[p][r - 1]);
		}
		if (r < SZ(g[p]) - 1)
		{
			mx = max(mx, R[p][r + 1]);
			mx2 = max(mx2, R2[p][r + 1]);
		}

		mx++;

		int e = g[x][ind];
		mx2 = max(mx2, S[E[e].y] - '0');

		E[e].depth = mx;
		E[e].any = mx2;
	}

	L[x].resize(SZ(g[x]));
	R[x].resize(SZ(g[x]));

	L2[x].resize(SZ(g[x]));
	R2[x].resize(SZ(g[x]));

	int mx = 0;
	int mx2 = 0;

	U[x] = INF;

	FOR (i, 0, SZ(g[x]))
	{
		int e = g[x][i];
		int val = E[e].depth;

		L[x][i] = R[x][i] = val;
		L2[x][i] = R2[x][i] = E[e].any;

		if (E[e].any)
		{
			U[x] = min(U[x], E[e].depth);
		}

		if (val > mx)
		{
			mx2 = mx;
			mx = val;
		}
		else
		{
			if (val > mx2)
			{
				mx2 = val;
			}
		}
	}

	D[x] = min(mx - 1, mx2 + 1);

	FOR (i, 1, SZ(g[x]))
	{
		L[x][i] = max(L[x][i], L[x][i-1]);
		L2[x][i] = max(L2[x][i], L2[x][i-1]);
	}

	RFOR(i, SZ(g[x]) - 1, 0)
	{
		R[x][i] = max(R[x][i], R[x][i+1]);
		R2[x][i] = max(R2[x][i], R2[x][i+1]);
	}



	FOR (i,0 , SZ(g[x]))
	{
		int e = g[x][i];
		int to = E[e].y;

		if (to == p) continue;
		dfs2(to, x, I[x][i]);
	}
}

int main()
{
	//freopen("in.txt", "r", stdin);
	//ios::sync_with_stdio(false); cin.tie(0);

	int n;
	scanf("%d", &n);
	FOR (i, 0, n-1)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		x--;
		y--;

		I[x].PB(SZ(g[y]));
		I[y].PB(SZ(g[x]));

		edge e;
		e.x = x; e.y = y;
		g[x].PB(SZ(E));
		E.PB(e);

		e.x = y; e.y = x;
		g[y].PB(SZ(E));
		E.PB(e);
	}

	scanf("%s", S);

	dfs1(0, -1);
	dfs2(0, -1, -1);

	LL res = 0;
	FOR (i, 0, n)
	{
		if (S[i] == '1') res += D[i] + 1;
		else
		{
			if (U[i] <= D[i])
			{
				res += D[i] - U[i] + 1;
			}
		}
	}
	res++;
	cout<<res<<endl;

	/*FOR (i, 0, n)
	{
		cout<<i<<' '<<D[i]<<' '<<U[i]<<endl;
	}
	cout<<endl;

	FOR (i, 0, SZ(E))
	{
		cout<<E[i].x<<' '<<E[i].y<<' '<<E[i].depth<<' '<<E[i].any<<endl;
	}*/



}

```