#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
const int MAXN=200005;
struct edge{int x,y,next;}a[2*MAXN];int len,last[MAXN];
void ins(int x,int y){len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;}
char ok[MAXN];int n;
int mx[2][MAXN],dep[MAXN],s[MAXN],in[MAXN],ot[MAXN],dfn;
void init(int x,int fa)
{
	in[x]=++dfn;s[dfn]=s[dfn-1]+ok[x]-'0';
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa)
		{
			init(y,x);dep[x]=max(dep[x],dep[y]+1);
			if(dep[y]+1>=mx[0][x])swap(mx[0][x],mx[1][x]),mx[0][x]=dep[y]+1;
			else if(dep[y]+1>=mx[1][x])mx[1][x]=dep[y]+1;
		}
	}ot[x]=dfn;
}
int upcal[MAXN];
void dp1(int x,int fa,int up)
{
	upcal[x]=up;
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa)
		{
			if(dep[y]+1==mx[0][x])dp1(y,x,max(up,mx[1][x])+1);
			else dp1(y,x,max(up,mx[0][x])+1);
		}
	}
}
int g(int l,int r){return s[r]-s[l-1];}
int du[MAXN];
int main()
{
	n=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		ins(x,y);ins(y,x);
		++du[x];++du[y];
	}scanf("%s",ok+1);
	init(1,0);dp1(1,0,0);
	LL ans=0;
	for(int i=1;i<len;i+=2)
	{
		int u=a[i].x,v=a[i].y;if(dep[u]>=dep[v])swap(u,v);
		int mx0=mx[0][u],mx1=(dep[u]+1==mx[0][v]?max(upcal[v],mx[1][v]):max(upcal[v],mx[0][v]));
		if(mx0<mx1&&g(in[u],ot[u]))++ans;
		else if(mx0>mx1&&(g(1,in[u]-1)+g(ot[u]+1,n)))++ans;
	}
	for(int i=1;i<=n;i++)
	{
		if(du[i]==1){ans+=ok[i]-'0';continue;}
		int mx0=mx[0][i],mx1=mx[1][i];
		if(upcal[i]>=mx0)swap(mx0,mx1),mx0=upcal[i];
		else if(upcal[i]>=mx1)mx1=upcal[i];
		int mn=999999999;
		for(int k=last[i];k;k=a[k].next)if(dep[a[k].y]<=dep[i])
		{
			int y=a[k].y;
			if(g(in[y],ot[y]))mn=min(mn,dep[y]+1);
		}if(g(in[i],in[i]))mn=0;
		if(g(1,in[i]-1)+g(ot[i]+1,n))mn=min(mn,upcal[i]);
		if(mn<=mx1)
		{
			if(mx0!=mx1)ans+=mx1-mn+1;
			else ans+=mx1-mn;
		}
	}
	if(g(1,n))++ans;
	pr2(ans);
	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<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline LL read()
{
	LL f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
template<typename T>inline void write(T x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
template<typename T>inline void pr1(T x){write(x);putchar(' ');}
template<typename T>inline void pr2(T x){write(x);putchar('\n');}
const int MAXN=200005;
struct edge{int x,y,next;}a[2*MAXN];int len,last[MAXN];
void ins(int x,int y){len++;a[len].x=x;a[len].y=y;a[len].next=last[x];last[x]=len;}
char ok[MAXN];int n;
int mx[2][MAXN],dep[MAXN],s[MAXN],in[MAXN],ot[MAXN],dfn;
void init(int x,int fa)
{
	in[x]=++dfn;s[dfn]=s[dfn-1]+ok[x]-'0';
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa)
		{
			init(y,x);dep[x]=max(dep[x],dep[y]+1);
			if(dep[y]+1>=mx[0][x])swap(mx[0][x],mx[1][x]),mx[0][x]=dep[y]+1;
			else if(dep[y]+1>=mx[1][x])mx[1][x]=dep[y]+1;
		}
	}ot[x]=dfn;
}
int upcal[MAXN];
void dp1(int x,int fa,int up)
{
	upcal[x]=up;
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa)
		{
			if(dep[y]+1==mx[0][x])dp1(y,x,max(up,mx[1][x])+1);
			else dp1(y,x,max(up,mx[0][x])+1);
		}
	}
}
int g(int l,int r){return s[r]-s[l-1];}
int du[MAXN];
int main()
{
	n=read();
	for(int i=1;i<n;i++)
	{
		int x=read(),y=read();
		ins(x,y);ins(y,x);
		++du[x];++du[y];
	}scanf("%s",ok+1);
	init(1,0);dp1(1,0,0);
	LL ans=0;
	for(int i=1;i<len;i+=2)
	{
		int u=a[i].x,v=a[i].y;if(dep[u]>=dep[v])swap(u,v);
		int mx0=mx[0][u],mx1=(dep[u]+1==mx[0][v]?max(upcal[v],mx[1][v]):max(upcal[v],mx[0][v]));
		if(mx0<mx1&&g(in[u],ot[u]))++ans;
		else if(mx0>mx1&&(g(1,in[u]-1)+g(ot[u]+1,n)))++ans;
	}
	for(int i=1;i<=n;i++)
	{
		if(du[i]==1){ans+=ok[i]-'0';continue;}
		int mx0=mx[0][i],mx1=mx[1][i];
		if(upcal[i]>=mx0)swap(mx0,mx1),mx0=upcal[i];
		else if(upcal[i]>=mx1)mx1=upcal[i];
		int mn=999999999;
		for(int k=last[i];k;k=a[k].next)if(dep[a[k].y]<=dep[i])
		{
			int y=a[k].y;
			if(g(in[y],ot[y]))mn=min(mn,dep[y]+1);
		}if(g(in[i],in[i]))mn=0;
		if(g(1,in[i]-1)+g(ot[i]+1,n))mn=min(mn,upcal[i]);
		if(mn<=mx1)
		{
			if(mx0!=mx1)ans+=mx1-mn+1;
			else ans+=mx1-mn;
		}
	}
	if(g(1,n))++ans;
	pr2(ans);
	return 0;
}

```