#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 200010
#define LL long long
using namespace std;

namespace Fenwick{
	int c[MAXN];

	void add(int x,int v){
		while(x<MAXN){
			c[x]+=v;
			x+=x&(-x);
		}
	}

	int sum(int x){
		int res=0;
		while(x){
			res+=c[x];
			x-=x&(-x);
		}
		return res;
	}
}

struct edge{
	int to,next;
	edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n;
int g[MAXN],nume,deg[MAXN];
int pre[MAXN],w[MAXN][2],numw;
int d[MAXN],d2[MAXN],d3[MAXN],d4[MAXN];
char type[MAXN];
LL ans;

void addEdge(int u,int v){
	e[nume]=edge(v,g[u]);
	g[u]=nume++;
}

void dfs(int x,int p){
	w[x][0]=++numw;
	d[x]=0;
	d3[x]=n+1;
	pre[x]=p;
	for(int i=g[x];~i;i=e[i].next)
		if(e[i].to^p){
			dfs(e[i].to,x);
			d[x]=max(d[x],d[e[i].to]+1);
			d3[x]=min(d3[x],d3[e[i].to]+1);
		}
	if(d3[x]==n+1) d3[x]=0;
	w[x][1]=numw;
}

void dfs2(int x,int p){
	pair<int,int> td1(-1,0),td2(-1,0);
	pair<int,int> td3(n+1,0),td4(n+1,0);
	if(p) td3=td1=make_pair(d2[x],0);
	else d4[x]=n+1;
	for(int i=g[x];~i;i=e[i].next)
		if(e[i].to^p){
			pair<int,int> temp=make_pair(d[e[i].to],e[i].to);
			if(temp>td1) td2=td1,td1=temp;
			else if(temp>td2) td2=temp;
			if(temp<td3) td4=td3,td3=temp;
			else if(temp<td4) td4=temp;
		}
	for(int i=g[x];~i;i=e[i].next)
		if(e[i].to^p){
			if(e[i].to==td1.second) d2[e[i].to]=td2.first+1;
			else d2[e[i].to]=td1.first+1;
			if(e[i].to!=td3.second) d4[e[i].to]=td3.first+1;
			else if(td4.first!=n+1) d4[e[i].to]=td4.first+1;
			else d4[e[i].to]=0;
			dfs2(e[i].to,x);
		}
}

void gao(int x){
	static pair<int,int> b[MAXN];
	int numb=0;
	for(int i=g[x];~i;i=e[i].next)
		if(e[i].to^pre[x])
			b[++numb]=make_pair(d[e[i].to]+1,Fenwick::sum(w[e[i].to][1])-Fenwick::sum(w[e[i].to][0]-1));
	if(pre[x])
		b[++numb]=make_pair(d2[x]+1,Fenwick::sum(n)-Fenwick::sum(w[x][1])+Fenwick::sum(w[x][0]-1));
	sort(b+1,b+numb+1);
	bool flag=(type[x]=='1');
	for(int i=0;i<numb;i++){
		if(b[i].second) flag=1;
		if(!flag) continue;
		if(i<numb-1) ans+=b[i+1].first-b[i].first;
		else{
			int t0=b[i].first;
			int t1=min(b[i+1].first-1,b[i].first+1);
			if(t0<=t1) ans+=t1-t0+1;
		}
	}
}

int main(){
#ifdef DEBUG
	freopen("F.in","r",stdin);
#endif
	memset(g,-1,sizeof g);
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		addEdge(u,v);
		addEdge(v,u);
		deg[u]++; deg[v]++;
	}
	scanf("%s",type+1);
	dfs(1,0);
	dfs2(1,0);
	ans++;
	for(int i=1;i<=n;i++) 
		if(type[i]=='1'){
			Fenwick::add(w[i][0],1);
			//if(deg[i]>1) ans+=min(d3[i],d4[i]+1);
			//else ans++;
		}
	for(int i=1;i<=n;i++) 
		gao(i);
	printf("%lld\n",ans);
	return 0;
}


### Prompt

Develop a solution in cpp to the problem described below:

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 <algorithm>
#define MAXN 200010
#define LL long long
using namespace std;

namespace Fenwick{
	int c[MAXN];

	void add(int x,int v){
		while(x<MAXN){
			c[x]+=v;
			x+=x&(-x);
		}
	}

	int sum(int x){
		int res=0;
		while(x){
			res+=c[x];
			x-=x&(-x);
		}
		return res;
	}
}

struct edge{
	int to,next;
	edge(int _to=0,int _next=0):to(_to),next(_next){}
}e[MAXN<<1];

int n;
int g[MAXN],nume,deg[MAXN];
int pre[MAXN],w[MAXN][2],numw;
int d[MAXN],d2[MAXN],d3[MAXN],d4[MAXN];
char type[MAXN];
LL ans;

void addEdge(int u,int v){
	e[nume]=edge(v,g[u]);
	g[u]=nume++;
}

void dfs(int x,int p){
	w[x][0]=++numw;
	d[x]=0;
	d3[x]=n+1;
	pre[x]=p;
	for(int i=g[x];~i;i=e[i].next)
		if(e[i].to^p){
			dfs(e[i].to,x);
			d[x]=max(d[x],d[e[i].to]+1);
			d3[x]=min(d3[x],d3[e[i].to]+1);
		}
	if(d3[x]==n+1) d3[x]=0;
	w[x][1]=numw;
}

void dfs2(int x,int p){
	pair<int,int> td1(-1,0),td2(-1,0);
	pair<int,int> td3(n+1,0),td4(n+1,0);
	if(p) td3=td1=make_pair(d2[x],0);
	else d4[x]=n+1;
	for(int i=g[x];~i;i=e[i].next)
		if(e[i].to^p){
			pair<int,int> temp=make_pair(d[e[i].to],e[i].to);
			if(temp>td1) td2=td1,td1=temp;
			else if(temp>td2) td2=temp;
			if(temp<td3) td4=td3,td3=temp;
			else if(temp<td4) td4=temp;
		}
	for(int i=g[x];~i;i=e[i].next)
		if(e[i].to^p){
			if(e[i].to==td1.second) d2[e[i].to]=td2.first+1;
			else d2[e[i].to]=td1.first+1;
			if(e[i].to!=td3.second) d4[e[i].to]=td3.first+1;
			else if(td4.first!=n+1) d4[e[i].to]=td4.first+1;
			else d4[e[i].to]=0;
			dfs2(e[i].to,x);
		}
}

void gao(int x){
	static pair<int,int> b[MAXN];
	int numb=0;
	for(int i=g[x];~i;i=e[i].next)
		if(e[i].to^pre[x])
			b[++numb]=make_pair(d[e[i].to]+1,Fenwick::sum(w[e[i].to][1])-Fenwick::sum(w[e[i].to][0]-1));
	if(pre[x])
		b[++numb]=make_pair(d2[x]+1,Fenwick::sum(n)-Fenwick::sum(w[x][1])+Fenwick::sum(w[x][0]-1));
	sort(b+1,b+numb+1);
	bool flag=(type[x]=='1');
	for(int i=0;i<numb;i++){
		if(b[i].second) flag=1;
		if(!flag) continue;
		if(i<numb-1) ans+=b[i+1].first-b[i].first;
		else{
			int t0=b[i].first;
			int t1=min(b[i+1].first-1,b[i].first+1);
			if(t0<=t1) ans+=t1-t0+1;
		}
	}
}

int main(){
#ifdef DEBUG
	freopen("F.in","r",stdin);
#endif
	memset(g,-1,sizeof g);
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int u,v;
		scanf("%d%d",&u,&v);
		addEdge(u,v);
		addEdge(v,u);
		deg[u]++; deg[v]++;
	}
	scanf("%s",type+1);
	dfs(1,0);
	dfs2(1,0);
	ans++;
	for(int i=1;i<=n;i++) 
		if(type[i]=='1'){
			Fenwick::add(w[i][0],1);
			//if(deg[i]>1) ans+=min(d3[i],d4[i]+1);
			//else ans++;
		}
	for(int i=1;i<=n;i++) 
		gao(i);
	printf("%lld\n",ans);
	return 0;
}


```