#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=201000;
int dep[N],p[N][22];
int n,u,v,mc,md,pu,pv,maxd[N],mad[N],l[N],shav[N];
ll ret;
VI e[N];
char fav[N];
void dfs(int u,int f,int dis) {
	p[u][0]=f; dep[u]=dis;
	if (dis>md) md=dis,mc=u;
	for (auto v:e[u]) if (v!=f) {
		dfs(v,u,dis+1);
	}
}
#define LOGN 18
int lca(int u,int v) {
	if (dep[u]>dep[v]) swap(u,v);
	per(i,0,LOGN) if (dep[p[v][i]]>=dep[u]) v=p[v][i];
	if (u==v) return u;
	per(i,0,LOGN) if (p[v][i]!=p[u][i]) u=p[u][i],v=p[v][i];
	return p[u][0];
}
int dist(int u,int v) {
	return dep[u]+dep[v]-2*dep[lca(u,v)];
}
void solve(int u,int f) {
	mad[u]=0;
	for (auto v:e[u]) if (v!=f) {
		solve(v,u);
		mad[u]=max(mad[u],mad[v]+1);
	}
	shav[u]=mad[u]+2; // if (u,d) d>=shav[u] -> (f,d-1)
	if (fav[u]=='1') l[u]=0;
//	printf("gg %d %d\n",u,maxd[u]);
	if (f!=0) {
		if (maxd[u]>maxd[f]) {
			l[f]=min(l[f],max(l[u]-1,shav[u]-1));
//			printf("ff %d %d %d\n",u,shav[u],l[u]);
			ret+=max(0,shav[u]-l[u]);
		} else {
			// double center
			shav[u]=maxd[u]; // d>=shav[u] -> (f,d)
			l[f]=min(l[f],max(l[u],shav[u]));
			ret+=max(0,shav[u]-l[u]);

		}
	} else ret+=max(0,maxd[u]-l[u]+1);
}
int main() {
	scanf("%d",&n);
	rep(i,1,n) {
		scanf("%d%d",&u,&v);
		e[u].pb(v); e[v].pb(u);
	}
	dfs(1,0,1);
	md=0;
	pu=mc;
	dfs(pu,0,1);
	rep(j,1,LOGN) rep(i,1,n+1) p[i][j]=p[p[i][j-1]][j-1];
	pv=mc;
	rep(i,1,n+1) maxd[i]=max(dist(i,pu),dist(i,pv));
//	printf("ss %d %d\n",pu,pv);
//	rep(i,1,n+1) printf("%d ",maxd[i]); puts("");
	int rt=min_element(maxd+1,maxd+n+1)-maxd;
//	printf("root %d\n",rt);
	scanf("%s",fav+1);
	rep(i,1,n+1) l[i]=1<<30;
	solve(rt,0);
	printf("%lld\n",ret);
}

### Prompt

Please provide a cpp coded solution 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 <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <cassert>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// head

const int N=201000;
int dep[N],p[N][22];
int n,u,v,mc,md,pu,pv,maxd[N],mad[N],l[N],shav[N];
ll ret;
VI e[N];
char fav[N];
void dfs(int u,int f,int dis) {
	p[u][0]=f; dep[u]=dis;
	if (dis>md) md=dis,mc=u;
	for (auto v:e[u]) if (v!=f) {
		dfs(v,u,dis+1);
	}
}
#define LOGN 18
int lca(int u,int v) {
	if (dep[u]>dep[v]) swap(u,v);
	per(i,0,LOGN) if (dep[p[v][i]]>=dep[u]) v=p[v][i];
	if (u==v) return u;
	per(i,0,LOGN) if (p[v][i]!=p[u][i]) u=p[u][i],v=p[v][i];
	return p[u][0];
}
int dist(int u,int v) {
	return dep[u]+dep[v]-2*dep[lca(u,v)];
}
void solve(int u,int f) {
	mad[u]=0;
	for (auto v:e[u]) if (v!=f) {
		solve(v,u);
		mad[u]=max(mad[u],mad[v]+1);
	}
	shav[u]=mad[u]+2; // if (u,d) d>=shav[u] -> (f,d-1)
	if (fav[u]=='1') l[u]=0;
//	printf("gg %d %d\n",u,maxd[u]);
	if (f!=0) {
		if (maxd[u]>maxd[f]) {
			l[f]=min(l[f],max(l[u]-1,shav[u]-1));
//			printf("ff %d %d %d\n",u,shav[u],l[u]);
			ret+=max(0,shav[u]-l[u]);
		} else {
			// double center
			shav[u]=maxd[u]; // d>=shav[u] -> (f,d)
			l[f]=min(l[f],max(l[u],shav[u]));
			ret+=max(0,shav[u]-l[u]);

		}
	} else ret+=max(0,maxd[u]-l[u]+1);
}
int main() {
	scanf("%d",&n);
	rep(i,1,n) {
		scanf("%d%d",&u,&v);
		e[u].pb(v); e[v].pb(u);
	}
	dfs(1,0,1);
	md=0;
	pu=mc;
	dfs(pu,0,1);
	rep(j,1,LOGN) rep(i,1,n+1) p[i][j]=p[p[i][j-1]][j-1];
	pv=mc;
	rep(i,1,n+1) maxd[i]=max(dist(i,pu),dist(i,pv));
//	printf("ss %d %d\n",pu,pv);
//	rep(i,1,n+1) printf("%d ",maxd[i]); puts("");
	int rt=min_element(maxd+1,maxd+n+1)-maxd;
//	printf("root %d\n",rt);
	scanf("%s",fav+1);
	rep(i,1,n+1) l[i]=1<<30;
	solve(rt,0);
	printf("%lld\n",ret);
}

```