#include <bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 200007;

int n;
LL ans;
AR(int) e[MAXN];
char s[MAXN];
bool cho[MAXN];
int lev[MAXN];
int aml[MAXN];

void init ();
void input ();
void work ();

int dfs1 ( int now, int fa );
void dfs2 ( int now, int fa, int al );

bool dfs ( int now, int fa, int nl, int al, int vu );



int main()
{
	init();
	input();
	work();
}



void init ()
{
	// Init Everything Here
	
	ios::sync_with_stdio ( false );
}

void input ()
{
	// input method
	
	scanf ( "%d", &n );
	int u, v;
	lp ( i, 1, n ){
		scanf ( "%d%d", &u, &v );
		e[u].PB ( v ), e[v].PB ( u );
	}
	scanf ( "%s", s );
}

void work ()
{
	// main work
	
	lpi ( i, 1, n ) cho[i] = s[i-1] == '1';
	
	if ( n == 2 ){
		int cc = 0;
		lpi ( i, 1, n ) cc += cho[i];
		cout << ( ( cc == 1 ) ? 2 : 3 ) << endl;
		return;
	}
	
	dfs1 ( 1, -1 );
	dfs2 ( 1, -1, 0 );
	int rt = min_element ( aml+1, aml+1+n ) - aml;
	dfs1 ( rt, -1 );
//	cerr << rt << endl;
//	for ( auto v : e[rt] ) cerr << v << " " << lev[v] << endl;
	
	dfs ( rt, -1, 0, -1, -MAXN );
	++ans;   // All black
	
	cout << ans << endl;
}



int dfs1 ( int now, int fa )
{
	lev[now] = 0;
	for ( auto v : e[now] ) if ( v ^ fa ) lev[now] = max ( lev[now], dfs1 ( v, now ) + 1 );
	return lev[now];
}

void dfs2 ( int now, int fa, int al )
{
	aml[now] = qmax ( lev[now], al );
	int maxi = -1, sm = -1;
	for ( auto v : e[now] ){
		if ( v ^ fa ){
			if ( lev[v] > maxi ) sm = maxi, maxi = lev[v];
			else if ( lev[v] > sm ) sm = lev[v];
		}
	}
	for ( auto v : e[now] ) if ( v ^ fa ) dfs2 ( v, now, max ( al, ( ( lev[v] == maxi ) ? sm : maxi ) + 1 ) + 1 );
}



bool dfs ( int now, int fa, int nl, int al, int vu )
{
//	cerr << now << " " << fa << " " << nl << " " << al << " " << vu << endl;
	
	if ( ~fa ) e[now].erase ( find ( e[now].begin (), e[now].end (), fa ) );
	if ( e[now].empty () ){
		if ( cho[now] ) ans += qmin ( al + nl, nl - vu );
		return cho[now];
	}
	
	sort ( e[now].begin (), e[now].end (), [] ( int x, int y ) { return lev[x] < lev[y]; } );
//	cerr << now << " : "; for ( auto v : e[now] ) cerr << v << " "; cerr << endl;
	
//	cerr << "nto : " << now << " : " << nto << endl;
//	cerr << now << " : " << lev[now]  << " " << sm << endl;
	bool nch = false;
	if ( al == -1 ) al = lev[now];
	if ( cho[now] ){
//		cerr << now << " : " << lev[now] << " : " << al << " " << nl << " " << vu << " " << lev[now] << " : " << qmin ( al + nl, nl - vu ) << endl;
		ans += qmin ( al + nl, nl - vu );
		nch = true;
	}
	
	for ( auto v : e[now] ){
		if ( fa == -1 && v == e[now].back () ) al = lev[*(e[now].rbegin()+1)] + 1;
		nch |= dfs ( v, now, nl + 1, al, max ( vu, nch ? ( nl - ( lev[v] + 1 ) ) : -INF ) );
	}
	
	return nch;
}
### Prompt

Please create a solution in cpp to 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 <bits/stdc++.h>
using namespace std;

#define LL long long
#define LD long double
#define SC(t,x) static_cast<t>(x)
#define AR(t) vector < t >
#define PII pair < int, int >
#define PLL pair < LL, LL >
#define PIL pair < int, LL >
#define PLI pair < LL, int >
#define MP make_pair
#define PB push_back
#define PF push_front
#define POB pop_back
#define POF pop_front
#define PRF first
#define PRS second
#define INIT(ar,val) memset ( ar, val, sizeof ( ar ) )
#define lp(loop,start,end) for ( int loop = start; loop < end; ++loop )
#define lpd(loop,start,end) for ( int loop = start; loop > end; --loop )
#define lpi(loop,start,end) for ( int loop = start; loop <= end; ++loop )
#define lpdi(loop,start,end) for ( int loop = start; loop >= end; --loop )
#define qmax(a,b) (((a)>(b))?(a):(b))
#define qmin(a,b) (((a)<(b))?(a):(b))
#define qabs(a) (((a)>=0)?(a):(-(a)))

const int INF = 0x3fffffff;
const int SINF = 0x7fffffff;
const long long LINF = 0x3fffffffffffffff;
const long long SLINF = 0x7fffffffffffffff;
const int MAXN = 200007;

int n;
LL ans;
AR(int) e[MAXN];
char s[MAXN];
bool cho[MAXN];
int lev[MAXN];
int aml[MAXN];

void init ();
void input ();
void work ();

int dfs1 ( int now, int fa );
void dfs2 ( int now, int fa, int al );

bool dfs ( int now, int fa, int nl, int al, int vu );



int main()
{
	init();
	input();
	work();
}



void init ()
{
	// Init Everything Here
	
	ios::sync_with_stdio ( false );
}

void input ()
{
	// input method
	
	scanf ( "%d", &n );
	int u, v;
	lp ( i, 1, n ){
		scanf ( "%d%d", &u, &v );
		e[u].PB ( v ), e[v].PB ( u );
	}
	scanf ( "%s", s );
}

void work ()
{
	// main work
	
	lpi ( i, 1, n ) cho[i] = s[i-1] == '1';
	
	if ( n == 2 ){
		int cc = 0;
		lpi ( i, 1, n ) cc += cho[i];
		cout << ( ( cc == 1 ) ? 2 : 3 ) << endl;
		return;
	}
	
	dfs1 ( 1, -1 );
	dfs2 ( 1, -1, 0 );
	int rt = min_element ( aml+1, aml+1+n ) - aml;
	dfs1 ( rt, -1 );
//	cerr << rt << endl;
//	for ( auto v : e[rt] ) cerr << v << " " << lev[v] << endl;
	
	dfs ( rt, -1, 0, -1, -MAXN );
	++ans;   // All black
	
	cout << ans << endl;
}



int dfs1 ( int now, int fa )
{
	lev[now] = 0;
	for ( auto v : e[now] ) if ( v ^ fa ) lev[now] = max ( lev[now], dfs1 ( v, now ) + 1 );
	return lev[now];
}

void dfs2 ( int now, int fa, int al )
{
	aml[now] = qmax ( lev[now], al );
	int maxi = -1, sm = -1;
	for ( auto v : e[now] ){
		if ( v ^ fa ){
			if ( lev[v] > maxi ) sm = maxi, maxi = lev[v];
			else if ( lev[v] > sm ) sm = lev[v];
		}
	}
	for ( auto v : e[now] ) if ( v ^ fa ) dfs2 ( v, now, max ( al, ( ( lev[v] == maxi ) ? sm : maxi ) + 1 ) + 1 );
}



bool dfs ( int now, int fa, int nl, int al, int vu )
{
//	cerr << now << " " << fa << " " << nl << " " << al << " " << vu << endl;
	
	if ( ~fa ) e[now].erase ( find ( e[now].begin (), e[now].end (), fa ) );
	if ( e[now].empty () ){
		if ( cho[now] ) ans += qmin ( al + nl, nl - vu );
		return cho[now];
	}
	
	sort ( e[now].begin (), e[now].end (), [] ( int x, int y ) { return lev[x] < lev[y]; } );
//	cerr << now << " : "; for ( auto v : e[now] ) cerr << v << " "; cerr << endl;
	
//	cerr << "nto : " << now << " : " << nto << endl;
//	cerr << now << " : " << lev[now]  << " " << sm << endl;
	bool nch = false;
	if ( al == -1 ) al = lev[now];
	if ( cho[now] ){
//		cerr << now << " : " << lev[now] << " : " << al << " " << nl << " " << vu << " " << lev[now] << " : " << qmin ( al + nl, nl - vu ) << endl;
		ans += qmin ( al + nl, nl - vu );
		nch = true;
	}
	
	for ( auto v : e[now] ){
		if ( fa == -1 && v == e[now].back () ) al = lev[*(e[now].rbegin()+1)] + 1;
		nch |= dfs ( v, now, nl + 1, al, max ( vu, nch ? ( nl - ( lev[v] + 1 ) ) : -INF ) );
	}
	
	return nch;
}
```