/*
下面只考虑所有不为全集的染色方案，最后再加上1表示全集的染色方案即可 
设F(u, d)表示距离u不超过d的点集
对于一个染色的方案S（显然是一个联通块），考虑其直径L
显然能让F(u, d) = S且d最小的u只会在直径的中点或中边的两个端点上，而所有直径的中点和中边都是相同的。分情况讨论： 
(1)L为偶数。那么F(u, d) = S且d最小的点，显然u只能是直径中点，d = L / 2
(2)L为奇数。那么整个树被中边(u, v)分成了两个根分别是u和v的子树，每一边子树尽量取一个非叶子的（取不到就取叶子）且能作为直径端点的端点
   不放设F(u, (L + 1) / 2) = S，那么u这边的端点一定是叶子，因为dist(u, u这边的端点) = (L - 1) / 2，若其不是叶子会产生矛盾
   同时，若F(v, (L + 1) / 2) = S，则S是整棵树，这是不合法的情况
综上所述，能让F(u, d) = S且d最小的u一定是S直径的中点或中边的两个端点，同时u是唯一的
这样一个显然的计数思路就是枚举u计算对应的S数量。称u和S对应，即F(u, d) = S且d最小
接下来考虑一个点u计算F(u, d)的贡献。为了方便把u当做整个树的根
*/
/*
设最大深度为d1，去掉最大深度所在的子树、剩下的子树中的最大深度为d2
首先d < d1，这是为了保证F(u, d)不是整棵树
考虑d2 < d1的情况。想象一个d从小到大变化的过程
                   当d = d2时，F(u, d)的直径为2 * d2且中点为u，一个端点在d2所在子树中、另一个端点在d1所在子树中
                   当d = d2 + 1时，d1所在子树中的端点继续向外延伸，u是中边的一个端点且仍然满足条件
		   当d = d2 + 2时，d1所在子树中的端点继续向外延伸，直径存在中点且不是u（是u向延伸方向的邻点），此时不符合条件
    综上所述，d < d2 + 2
所以，只要d < min{d1, d2 + 2}，F(u, d)这个点集对应的点就是u
*/
/*
还要考虑的问题是，若u未被染黑则需存在一个被染黑的点v满足F(v, k > d) = F(u, d)  
显然满足条件则一定有k = d + dist(u, v)，并且此时一定满足F(u, d)是F(v, k)的子集。下面判断F(v, k)是否是F(u, d)的子集 
设v在u的儿子m所代表的子树中，那么F(m, d < d + 1)是F(v, k)的子集，那么合法的必要条件是m向下延伸的最远距离 < d，考虑u到v路径上所有点可以发现这也是充分条件
这个条件直观描述就是：m子树中所有点都被染黑
所以找到一个含有被染黑节点且深度最小的子树m，设m向下延伸的最远距离为d3，则d > d3
*/
/*
综上已经对于每个u找到了d的上界和下界，直接计算即可
*/

#include <cstdio>
#include <algorithm>

using namespace std;
const int Max_N(200050);
typedef long long int LL;

int N, Head[Max_N], Total, To[Max_N << 1], Next[Max_N << 1], Size[Max_N], F1[Max_N], F2[Max_N];
char B[Max_N];
LL Ans;

inline void Add_Edge(int s, int t)
{
	++Total, To[Total] = t, Next[Total] = Head[s], Head[s] = Total;
}

void dfs(int u, int fa)
{
	Size[u] = B[u] - '0';
	for (int i = Head[u], v;i;i = Next[i])
		if ((v = To[i]) != fa)
		{
			dfs(v, u), Size[u] += Size[v];
			if (F1[v] + 1 >= F1[u])
				F2[u] = F1[u], F1[u] = F1[v] + 1;
			else
				if (F1[v] + 1 >= F2[u])
					F2[u] = F1[v] + 1;
		}
}

void work(int u, int fa)
{
	int l, r;//[l, r)
	l = (B[u] == '1' ? 0 : N + 1);
	if (fa != -1)
	{
		int d = (F1[fa] == F1[u] + 1 ? F2[fa] : F1[fa]);
		if (Size[1] - Size[u])
			l = min(l, d + 1);
		if (d + 1 >= F1[u])
			F2[u] = F1[u], F1[u] = d + 1;
		else
			if (d + 1 >= F2[u])
				F2[u] = d + 1;
	}
	r = min(F1[u], F2[u] + 2);
	for (int i = Head[u], v;i;i = Next[i])
		if ((v = To[i]) != fa)
		{
			if (Size[v])
				l = min(l, F1[v] + 1);
			work(v, u);
		}
	if (l <= r - 1)
		Ans += r - l;
}

int main()
{
	scanf("%d", &N);
	for (int i = 1, u, v;i != N;++i)
		scanf("%d%d", &u, &v), Add_Edge(u, v), Add_Edge(v, u);
	scanf("%s", B + 1);
	dfs(1, -1), work(1, -1);
	printf("%lld", Ans + 1LL);
	return 0;
}
### Prompt

In CPP, your task is to solve 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
/*
下面只考虑所有不为全集的染色方案，最后再加上1表示全集的染色方案即可 
设F(u, d)表示距离u不超过d的点集
对于一个染色的方案S（显然是一个联通块），考虑其直径L
显然能让F(u, d) = S且d最小的u只会在直径的中点或中边的两个端点上，而所有直径的中点和中边都是相同的。分情况讨论： 
(1)L为偶数。那么F(u, d) = S且d最小的点，显然u只能是直径中点，d = L / 2
(2)L为奇数。那么整个树被中边(u, v)分成了两个根分别是u和v的子树，每一边子树尽量取一个非叶子的（取不到就取叶子）且能作为直径端点的端点
   不放设F(u, (L + 1) / 2) = S，那么u这边的端点一定是叶子，因为dist(u, u这边的端点) = (L - 1) / 2，若其不是叶子会产生矛盾
   同时，若F(v, (L + 1) / 2) = S，则S是整棵树，这是不合法的情况
综上所述，能让F(u, d) = S且d最小的u一定是S直径的中点或中边的两个端点，同时u是唯一的
这样一个显然的计数思路就是枚举u计算对应的S数量。称u和S对应，即F(u, d) = S且d最小
接下来考虑一个点u计算F(u, d)的贡献。为了方便把u当做整个树的根
*/
/*
设最大深度为d1，去掉最大深度所在的子树、剩下的子树中的最大深度为d2
首先d < d1，这是为了保证F(u, d)不是整棵树
考虑d2 < d1的情况。想象一个d从小到大变化的过程
                   当d = d2时，F(u, d)的直径为2 * d2且中点为u，一个端点在d2所在子树中、另一个端点在d1所在子树中
                   当d = d2 + 1时，d1所在子树中的端点继续向外延伸，u是中边的一个端点且仍然满足条件
		   当d = d2 + 2时，d1所在子树中的端点继续向外延伸，直径存在中点且不是u（是u向延伸方向的邻点），此时不符合条件
    综上所述，d < d2 + 2
所以，只要d < min{d1, d2 + 2}，F(u, d)这个点集对应的点就是u
*/
/*
还要考虑的问题是，若u未被染黑则需存在一个被染黑的点v满足F(v, k > d) = F(u, d)  
显然满足条件则一定有k = d + dist(u, v)，并且此时一定满足F(u, d)是F(v, k)的子集。下面判断F(v, k)是否是F(u, d)的子集 
设v在u的儿子m所代表的子树中，那么F(m, d < d + 1)是F(v, k)的子集，那么合法的必要条件是m向下延伸的最远距离 < d，考虑u到v路径上所有点可以发现这也是充分条件
这个条件直观描述就是：m子树中所有点都被染黑
所以找到一个含有被染黑节点且深度最小的子树m，设m向下延伸的最远距离为d3，则d > d3
*/
/*
综上已经对于每个u找到了d的上界和下界，直接计算即可
*/

#include <cstdio>
#include <algorithm>

using namespace std;
const int Max_N(200050);
typedef long long int LL;

int N, Head[Max_N], Total, To[Max_N << 1], Next[Max_N << 1], Size[Max_N], F1[Max_N], F2[Max_N];
char B[Max_N];
LL Ans;

inline void Add_Edge(int s, int t)
{
	++Total, To[Total] = t, Next[Total] = Head[s], Head[s] = Total;
}

void dfs(int u, int fa)
{
	Size[u] = B[u] - '0';
	for (int i = Head[u], v;i;i = Next[i])
		if ((v = To[i]) != fa)
		{
			dfs(v, u), Size[u] += Size[v];
			if (F1[v] + 1 >= F1[u])
				F2[u] = F1[u], F1[u] = F1[v] + 1;
			else
				if (F1[v] + 1 >= F2[u])
					F2[u] = F1[v] + 1;
		}
}

void work(int u, int fa)
{
	int l, r;//[l, r)
	l = (B[u] == '1' ? 0 : N + 1);
	if (fa != -1)
	{
		int d = (F1[fa] == F1[u] + 1 ? F2[fa] : F1[fa]);
		if (Size[1] - Size[u])
			l = min(l, d + 1);
		if (d + 1 >= F1[u])
			F2[u] = F1[u], F1[u] = d + 1;
		else
			if (d + 1 >= F2[u])
				F2[u] = d + 1;
	}
	r = min(F1[u], F2[u] + 2);
	for (int i = Head[u], v;i;i = Next[i])
		if ((v = To[i]) != fa)
		{
			if (Size[v])
				l = min(l, F1[v] + 1);
			work(v, u);
		}
	if (l <= r - 1)
		Ans += r - l;
}

int main()
{
	scanf("%d", &N);
	for (int i = 1, u, v;i != N;++i)
		scanf("%d%d", &u, &v), Add_Edge(u, v), Add_Edge(v, u);
	scanf("%s", B + 1);
	dfs(1, -1), work(1, -1);
	printf("%lld", Ans + 1LL);
	return 0;
}
```