#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define SZ 666666
int n,M=0,fst[SZ],vb[SZ],nxt[SZ];
void ad_de(int a,int b)
{
	++M; nxt[M]=fst[a]; fst[a]=M; vb[M]=b;
}
void adde(int a,int b)
{
	ad_de(a,b);ad_de(b,a);
}
int md[SZ],mu[SZ],fa[SZ];
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
void dfs(int x,int f=0)
{
	fa[x]=f;
	for esb(x,e,b) if(b!=f)
	{
		dfs(b,x); md[x]=max(md[x],md[b]);
	}
	++md[x];
}
typedef long long ll;
char c[SZ];
bool q[SZ],h[SZ],zs[SZ]; int dfn[SZ],C=0,ls[SZ];
void dfs2(int x,int f=0)
{
	int cm=mu[x]+1; dfn[x]=++C;
	if(c[x]=='1') q[C]=h[C]=zs[x]=1;
	vector<int> vs;
	for esb(x,e,b) if(b!=f) vs.push_back(b);
	for(int i=0;i<vs.size();++i)
	{
		int v=vs[i];
		mu[v]=max(mu[v],cm);
		cm=max(cm,md[v]+2);
	}
	cm=mu[x]+1;
	for(int i=int(vs.size())-1;i>=0;--i)
	{
		int v=vs[i];
		mu[v]=max(mu[v],cm);
		cm=max(cm,md[v]+2);
	}
	vs.clear();
	for esb(x,e,b) if(b!=f)
		dfs2(b,x),zs[x]|=zs[b];
	ls[x]=C;
}
int dd[SZ],uu[SZ];
void doit(int x)
{
	vector<int> v;
	v.push_back(mu[x]-1);
	for esb(x,e,b) if(b!=fa[x]) v.push_back(md[b]);
	sort(v.begin(),v.end());
	int p=v[v.size()-1]-1;
	if(v.size()>1) p=min(p,v[v.size()-2]+1);
	else p=min(p,1);
	dd[x]=p; uu[x]=1e9; if(c[x]=='1') uu[x]=0;
	for esb(x,e,b) if(b!=fa[x]) if(zs[b]) uu[x]=min(uu[x],md[b]);
	if(q[dfn[x]-1]||h[ls[x]+1]) uu[x]=min(uu[x],mu[x]-1);
}
int main()
{
	scanf("%d",&n);
	for(int i=1,a,b;i<n;++i)
		scanf("%d%d",&a,&b),adde(a,b);
	scanf("%s",c+1); dfs(1); mu[1]=1; dfs2(1);
	for(int i=1;i<=C;++i) q[i]|=q[i-1];
	for(int i=C;i>=1;--i) h[i]|=h[i+1];
	ll ans=1;
	for(int i=1;i<=n;++i)
		doit(i), ans+=max(dd[i]-uu[i]+1,0);
	printf("%lld\n",ans);
}
### 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 <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
#define SZ 666666
int n,M=0,fst[SZ],vb[SZ],nxt[SZ];
void ad_de(int a,int b)
{
	++M; nxt[M]=fst[a]; fst[a]=M; vb[M]=b;
}
void adde(int a,int b)
{
	ad_de(a,b);ad_de(b,a);
}
int md[SZ],mu[SZ],fa[SZ];
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
void dfs(int x,int f=0)
{
	fa[x]=f;
	for esb(x,e,b) if(b!=f)
	{
		dfs(b,x); md[x]=max(md[x],md[b]);
	}
	++md[x];
}
typedef long long ll;
char c[SZ];
bool q[SZ],h[SZ],zs[SZ]; int dfn[SZ],C=0,ls[SZ];
void dfs2(int x,int f=0)
{
	int cm=mu[x]+1; dfn[x]=++C;
	if(c[x]=='1') q[C]=h[C]=zs[x]=1;
	vector<int> vs;
	for esb(x,e,b) if(b!=f) vs.push_back(b);
	for(int i=0;i<vs.size();++i)
	{
		int v=vs[i];
		mu[v]=max(mu[v],cm);
		cm=max(cm,md[v]+2);
	}
	cm=mu[x]+1;
	for(int i=int(vs.size())-1;i>=0;--i)
	{
		int v=vs[i];
		mu[v]=max(mu[v],cm);
		cm=max(cm,md[v]+2);
	}
	vs.clear();
	for esb(x,e,b) if(b!=f)
		dfs2(b,x),zs[x]|=zs[b];
	ls[x]=C;
}
int dd[SZ],uu[SZ];
void doit(int x)
{
	vector<int> v;
	v.push_back(mu[x]-1);
	for esb(x,e,b) if(b!=fa[x]) v.push_back(md[b]);
	sort(v.begin(),v.end());
	int p=v[v.size()-1]-1;
	if(v.size()>1) p=min(p,v[v.size()-2]+1);
	else p=min(p,1);
	dd[x]=p; uu[x]=1e9; if(c[x]=='1') uu[x]=0;
	for esb(x,e,b) if(b!=fa[x]) if(zs[b]) uu[x]=min(uu[x],md[b]);
	if(q[dfn[x]-1]||h[ls[x]+1]) uu[x]=min(uu[x],mu[x]-1);
}
int main()
{
	scanf("%d",&n);
	for(int i=1,a,b;i<n;++i)
		scanf("%d%d",&a,&b),adde(a,b);
	scanf("%s",c+1); dfs(1); mu[1]=1; dfs2(1);
	for(int i=1;i<=C;++i) q[i]|=q[i-1];
	for(int i=C;i>=1;--i) h[i]|=h[i+1];
	ll ans=1;
	for(int i=1;i<=n;++i)
		doit(i), ans+=max(dd[i]-uu[i]+1,0);
	printf("%lld\n",ans);
}
```