#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define int long long
using namespace std;
inline int read(){
	int f=1,ans=0;char c;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
	return ans*f;
}
const int N=200011;
int cnt,d1[N],d2[N],d3[N],head[N],n,siz[N];
/*d1到叶子节点最长路径*/
/*d2为除掉一个子树的最长路径*/
/*d3为下界*/
struct node{
	int u,v,nex;
}x[N<<1];
void add(int u,int v){
	x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++;
}
int son[N],sum;
char str[N];
void dfs1(int f,int fath){
	if(str[f]=='1') siz[f]=1,d3[f]=0,sum++;
	for(int i=head[f];i!=-1;i=x[i].nex){
		if(x[i].v==fath) continue;
		dfs1(x[i].v,f);
		if(d1[x[i].v]+1>=d1[f]) son[f]=x[i].v,d2[f]=d1[f],d1[f]=d1[x[i].v]+1;
		else if(d1[x[i].v]+1>=d2[f]) d2[f]=d1[x[i].v]+1;
		if(siz[x[i].v]) d3[f]=min(d3[f],d1[x[i].v]+1);
		siz[f]+=siz[x[i].v];
	}return; 
}
void dfs2(int f,int fath,int v){
	int nowv;
	for(int i=head[f];i!=-1;i=x[i].nex){
		
		if(x[i].v==fath) continue;
		
		if(son[f]==x[i].v) nowv=max(v,d2[f])+1;
		else nowv=max(v,d1[f])+1;
		
		if(nowv>=d1[x[i].v]) d2[x[i].v]=d1[x[i].v],d1[x[i].v]=nowv;
		else if(nowv>d2[x[i].v]) d2[x[i].v]=nowv;
		
		if(sum-siz[x[i].v]) d3[x[i].v]=min(d3[x[i].v],nowv);
		dfs2(x[i].v,f,nowv);
	}
}int ans;
signed main(){
//	freopen("make.in","r",stdin);
	memset(head,-1,sizeof(head));
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
	scanf("%s",str+1);
	memset(d3,127,sizeof(d3));
	dfs1(1,0);

	dfs2(1,0,0);
//	for(int i=1;i<=n;i++) printf("d1(%d):%d d2(%d):%d d3(%d):%d\n",i,d1[i],i,d2[i],i,d3[i]);
	for(int i=1;i<=n;i++){
		if(str[i]=='1') ans+=max(min(d1[i],d2[i]+2),0LL);
		else ans+=max(min(d1[i],d2[i]+2)-d3[i],0LL);
	}printf("%lld\n",ans+1);
}

### Prompt

Create a solution in cpp for 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<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define int long long
using namespace std;
inline int read(){
	int f=1,ans=0;char c;
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}
	return ans*f;
}
const int N=200011;
int cnt,d1[N],d2[N],d3[N],head[N],n,siz[N];
/*d1到叶子节点最长路径*/
/*d2为除掉一个子树的最长路径*/
/*d3为下界*/
struct node{
	int u,v,nex;
}x[N<<1];
void add(int u,int v){
	x[cnt].u=u,x[cnt].v=v,x[cnt].nex=head[u],head[u]=cnt++;
}
int son[N],sum;
char str[N];
void dfs1(int f,int fath){
	if(str[f]=='1') siz[f]=1,d3[f]=0,sum++;
	for(int i=head[f];i!=-1;i=x[i].nex){
		if(x[i].v==fath) continue;
		dfs1(x[i].v,f);
		if(d1[x[i].v]+1>=d1[f]) son[f]=x[i].v,d2[f]=d1[f],d1[f]=d1[x[i].v]+1;
		else if(d1[x[i].v]+1>=d2[f]) d2[f]=d1[x[i].v]+1;
		if(siz[x[i].v]) d3[f]=min(d3[f],d1[x[i].v]+1);
		siz[f]+=siz[x[i].v];
	}return; 
}
void dfs2(int f,int fath,int v){
	int nowv;
	for(int i=head[f];i!=-1;i=x[i].nex){
		
		if(x[i].v==fath) continue;
		
		if(son[f]==x[i].v) nowv=max(v,d2[f])+1;
		else nowv=max(v,d1[f])+1;
		
		if(nowv>=d1[x[i].v]) d2[x[i].v]=d1[x[i].v],d1[x[i].v]=nowv;
		else if(nowv>d2[x[i].v]) d2[x[i].v]=nowv;
		
		if(sum-siz[x[i].v]) d3[x[i].v]=min(d3[x[i].v],nowv);
		dfs2(x[i].v,f,nowv);
	}
}int ans;
signed main(){
//	freopen("make.in","r",stdin);
	memset(head,-1,sizeof(head));
	n=read();
	for(int i=1;i<n;i++){
		int u=read(),v=read();
		add(u,v),add(v,u);
	}
	scanf("%s",str+1);
	memset(d3,127,sizeof(d3));
	dfs1(1,0);

	dfs2(1,0,0);
//	for(int i=1;i<=n;i++) printf("d1(%d):%d d2(%d):%d d3(%d):%d\n",i,d1[i],i,d2[i],i,d3[i]);
	for(int i=1;i<=n;i++){
		if(str[i]=='1') ans+=max(min(d1[i],d2[i]+2),0LL);
		else ans+=max(min(d1[i],d2[i]+2)-d3[i],0LL);
	}printf("%lld\n",ans+1);
}

```