#include<bits/stdc++.h>
#define inf 1000000000
#define N 200009
using namespace std;

int n,tot,cnt,tp,dfsclk,q[N],fst[N],pnt[N<<1],nxt[N<<1];
int lf[N],rg[N],id[N],anc[N],sz[N],son[N],fa[N],d[N],f[N];
long long ans; char s[N];
struct node{ int x,y; }a[N],b[N],c[N];
bool operator <(node u,node v){ return u.x<v.x; }
void mdy(node &u,node v){
	u.x=max(u.x,v.x); u.y=min(u.y,v.y);
}
void add(int x,int y){
	pnt[++tot]=y; nxt[tot]=fst[x]; fst[x]=tot;
}
int find(int x,int y){
	int t=x;
	for (; anc[x]!=anc[y]; x=fa[anc[x]]) t=anc[x];
	return x==y?t:id[lf[y]+1];
}
void calc(int x){
	int i,y;
	if (b[x].x) c[cnt=1]=b[x]; else cnt=0;
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]) c[++cnt]=a[y];
	}
	sort(c+1,c+cnt+1);
	int l=0,r=c[cnt].x-1;
	if (b[x].x==c[cnt].x) r=min(r,a[x].x);
	else{
		for (i=fst[x]; i; i=nxt[i]){
			y=pnt[i];
			if (y!=fa[x] && c[cnt].x==a[y].x){
				r=min(r,b[y].x); break;
			}
		}
	}
	//cout<<x<<endl;
	if (s[x]=='0'){
		l=inf;
		for (i=1; i<=cnt; i++){
			//y=c[i].y;
			//if (!y) continue;
			if (c[i].y<inf) l=min(l,c[i].x);
			//else l=min(l,c[i].y+c[cnt-1].x+c[i].y);
			//cout<<"?	"<<y<<endl;
			//if (lf[y]<=lf[x] && lf[x]<=rg[y]){
			//	y=find(x,y);
			//	cout<<"	"<<c[i].z<<endl;
			//}
			//else{
			//	cout<<"	"<<c[i].z<<' '<<b[y].x<<endl;
			//	l=min(l,c[i].z+b[y].x-1);
			//}
		}
	}
	//cout<<"  "<<l<<' '<<r<<endl;
	ans+=max(0,r-l+1);
}
void dfs(int x){
	int i,y; sz[x]=1;
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]){
			fa[y]=x; d[y]=d[x]+1;
			dfs(y); sz[x]+=sz[y];
			if (sz[y]>sz[son[x]]) son[x]=y;
			mdy(a[x],a[y]);
		}
	}
	a[x].x++; a[x].y++;
	if (s[x]=='1') a[x].y=1;
}
void dvd(int x,int tp){
	int i,y;
	lf[x]=++dfsclk; id[dfsclk]=x; anc[x]=tp;
	if (son[x]) dvd(son[x],tp);
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x] && y!=son[x]) dvd(y,y);
	}
	rg[x]=dfsclk;
}
void dfs2(int x){
	int i,y;
	for (i=fst[x],tp=0; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]) q[++tp]=y;
	}
	node tmp=b[x];
	for (i=1; i<=tp; i++){
		y=q[i];
		mdy(b[y],tmp);
		mdy(tmp,a[y]);
	}
	for (i=tp,tmp=(node){-inf,inf}; i; i--){
		y=q[i];
		mdy(b[y],tmp);
		mdy(tmp,a[y]);
	}
	for (i=1; i<=tp; i++){
		b[q[i]].x++; b[q[i]].y++;
	}
	if (s[x]=='1')
		for (i=1; i<=tp; i++){
			b[q[i]].y=1;// b[q[i]].z=1;
		}
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]) dfs2(y);
	}
}
int main(){
	scanf("%d",&n);
	int i,x,y;
	for (i=1; i<n; i++){
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	scanf("%s",s+1);
	for (i=1; i<=n; i++) a[i].y=b[i].y=inf;
	dfs(1); dvd(1,1); dfs2(1);
	for (i=1; i<=n; i++) calc(i);
	printf("%lld\n",ans+1);
	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<bits/stdc++.h>
#define inf 1000000000
#define N 200009
using namespace std;

int n,tot,cnt,tp,dfsclk,q[N],fst[N],pnt[N<<1],nxt[N<<1];
int lf[N],rg[N],id[N],anc[N],sz[N],son[N],fa[N],d[N],f[N];
long long ans; char s[N];
struct node{ int x,y; }a[N],b[N],c[N];
bool operator <(node u,node v){ return u.x<v.x; }
void mdy(node &u,node v){
	u.x=max(u.x,v.x); u.y=min(u.y,v.y);
}
void add(int x,int y){
	pnt[++tot]=y; nxt[tot]=fst[x]; fst[x]=tot;
}
int find(int x,int y){
	int t=x;
	for (; anc[x]!=anc[y]; x=fa[anc[x]]) t=anc[x];
	return x==y?t:id[lf[y]+1];
}
void calc(int x){
	int i,y;
	if (b[x].x) c[cnt=1]=b[x]; else cnt=0;
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]) c[++cnt]=a[y];
	}
	sort(c+1,c+cnt+1);
	int l=0,r=c[cnt].x-1;
	if (b[x].x==c[cnt].x) r=min(r,a[x].x);
	else{
		for (i=fst[x]; i; i=nxt[i]){
			y=pnt[i];
			if (y!=fa[x] && c[cnt].x==a[y].x){
				r=min(r,b[y].x); break;
			}
		}
	}
	//cout<<x<<endl;
	if (s[x]=='0'){
		l=inf;
		for (i=1; i<=cnt; i++){
			//y=c[i].y;
			//if (!y) continue;
			if (c[i].y<inf) l=min(l,c[i].x);
			//else l=min(l,c[i].y+c[cnt-1].x+c[i].y);
			//cout<<"?	"<<y<<endl;
			//if (lf[y]<=lf[x] && lf[x]<=rg[y]){
			//	y=find(x,y);
			//	cout<<"	"<<c[i].z<<endl;
			//}
			//else{
			//	cout<<"	"<<c[i].z<<' '<<b[y].x<<endl;
			//	l=min(l,c[i].z+b[y].x-1);
			//}
		}
	}
	//cout<<"  "<<l<<' '<<r<<endl;
	ans+=max(0,r-l+1);
}
void dfs(int x){
	int i,y; sz[x]=1;
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]){
			fa[y]=x; d[y]=d[x]+1;
			dfs(y); sz[x]+=sz[y];
			if (sz[y]>sz[son[x]]) son[x]=y;
			mdy(a[x],a[y]);
		}
	}
	a[x].x++; a[x].y++;
	if (s[x]=='1') a[x].y=1;
}
void dvd(int x,int tp){
	int i,y;
	lf[x]=++dfsclk; id[dfsclk]=x; anc[x]=tp;
	if (son[x]) dvd(son[x],tp);
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x] && y!=son[x]) dvd(y,y);
	}
	rg[x]=dfsclk;
}
void dfs2(int x){
	int i,y;
	for (i=fst[x],tp=0; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]) q[++tp]=y;
	}
	node tmp=b[x];
	for (i=1; i<=tp; i++){
		y=q[i];
		mdy(b[y],tmp);
		mdy(tmp,a[y]);
	}
	for (i=tp,tmp=(node){-inf,inf}; i; i--){
		y=q[i];
		mdy(b[y],tmp);
		mdy(tmp,a[y]);
	}
	for (i=1; i<=tp; i++){
		b[q[i]].x++; b[q[i]].y++;
	}
	if (s[x]=='1')
		for (i=1; i<=tp; i++){
			b[q[i]].y=1;// b[q[i]].z=1;
		}
	for (i=fst[x]; i; i=nxt[i]){
		y=pnt[i];
		if (y!=fa[x]) dfs2(y);
	}
}
int main(){
	scanf("%d",&n);
	int i,x,y;
	for (i=1; i<n; i++){
		scanf("%d%d",&x,&y);
		add(x,y); add(y,x);
	}
	scanf("%s",s+1);
	for (i=1; i<=n; i++) a[i].y=b[i].y=inf;
	dfs(1); dvd(1,1); dfs2(1);
	for (i=1; i<=n; i++) calc(i);
	printf("%lld\n",ans+1);
	return 0;
}

```