#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;
 
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))
 
const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
 
const ll M = 1000000007;
 
vector<int> G[200010];
vector<int> rid[200010];
vector<P> dp_ord;
vector<int> dep[200010];
vector<int> cnt[200010];
P max_dep[200010][2];
int sum_cnt[200010];
bool s_[200010];
void make_ord_dfs1(int v,int p){
	for(int i = 0 ; i < G[v].size() ; i ++){
		if(G[v][i] != p){
			make_ord_dfs1(G[v][i],v);
			dp_ord.pb(P(v,i));
		}
	}
}
void make_ord_dfs2(int v,int p){
	for(int i = 0 ; i < G[v].size() ; i ++){
		if(G[v][i] == p){
			dp_ord.pb(P(v,i));
			break;
		}
	}
	for(int i = 0 ; i < G[v].size() ; i ++){
		if(G[v][i] != p){
			make_ord_dfs2(G[v][i],v);
		}
	}
}
void make_ord(){
	make_ord_dfs1(1,0);
	make_ord_dfs2(1,0);
}
void dfs(int v,int id){
	int u = G[v][id];
	if(max_dep[u][0].sc != rid[v][id])dep[v][id] = max_dep[u][0].fr+1;
	else dep[v][id] = max_dep[u][1].fr+1;
	cnt[v][id] = sum_cnt[u]-cnt[u][rid[v][id]]+(s_[u]?1:0);
	if(max_dep[v][1] < P(dep[v][id],id)){
		max_dep[v][1] = P(dep[v][id],id);
		if(max_dep[v][0] < max_dep[v][1])swap(max_dep[v][0],max_dep[v][1]);
	}
	sum_cnt[v] += cnt[v][id];
}
 
int main(){
	static int n;
	static int a[200010],b[200010];
	string s;
	scanf("%d",&n);
	rep1(i,n-1)scanf("%d%d",&a[i],&b[i]);
	cin >> s;
	
	rep1(i,n-1){
		rid[a[i]].pb(G[b[i]].size());
		rid[b[i]].pb(G[a[i]].size());
		G[a[i]].pb(b[i]);
		G[b[i]].pb(a[i]);
		dep[a[i]].pb(0);
		cnt[a[i]].pb(0);
		dep[b[i]].pb(0);
		cnt[b[i]].pb(0);
	}
	rep1(i,n){
		max_dep[i][0] = P(0,-1);
		max_dep[i][1] = P(0,-1);
		sum_cnt[i] = 0;
	}
	rep1(i,n){
		if(s[i-1] == '1')s_[i] = true;
		else s_[i] = false;
	}
	
	make_ord();
	for(P p: dp_ord){
		dfs(p.fr,p.sc);
	}
	
	ll ret = 0;
	rep1(i,n){
		vector<P> vec;
		rep(j,G[i].size()){
			vec.pb(P(dep[i][j],cnt[i][j]));
		}
		vec.pb(P(0,(s_[i]?1:0)));
		sor(vec);
		int d_max = vec[vec.size()-1].fr;
		int k = vec.size()-2;
		int I = 0;
		while(I+1 < vec.size() && vec[I].sc == 0)I ++;
		ret += max( min( d_max , vec[k].fr+2 ) - vec[I].fr , 0 );
	}
	cout << ret+1 << endl;
}
### Prompt

Your task is to create a CPP solution 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<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<string>
#include<stack>
#include<cstdio>
#include<cmath>
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
typedef pair<int,P> P1;
 
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
#define rep(i,x) for(int i=0;i<x;i++)
#define rep1(i,x) for(int i=1;i<=x;i++)
#define rrep(i,x) for(int i=x-1;i>=0;i--)
#define rrep1(i,x) for(int i=x;i>0;i--)
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
#define mp1(a,b,c) P1(a,P(b,c))
 
const int INF=1000000000;
const int dir_4[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
const int dir_8[8][2]={{1,0},{1,1},{0,1},{-1,1},{-1,0},{-1,-1},{0,-1},{1,-1}};
 
const ll M = 1000000007;
 
vector<int> G[200010];
vector<int> rid[200010];
vector<P> dp_ord;
vector<int> dep[200010];
vector<int> cnt[200010];
P max_dep[200010][2];
int sum_cnt[200010];
bool s_[200010];
void make_ord_dfs1(int v,int p){
	for(int i = 0 ; i < G[v].size() ; i ++){
		if(G[v][i] != p){
			make_ord_dfs1(G[v][i],v);
			dp_ord.pb(P(v,i));
		}
	}
}
void make_ord_dfs2(int v,int p){
	for(int i = 0 ; i < G[v].size() ; i ++){
		if(G[v][i] == p){
			dp_ord.pb(P(v,i));
			break;
		}
	}
	for(int i = 0 ; i < G[v].size() ; i ++){
		if(G[v][i] != p){
			make_ord_dfs2(G[v][i],v);
		}
	}
}
void make_ord(){
	make_ord_dfs1(1,0);
	make_ord_dfs2(1,0);
}
void dfs(int v,int id){
	int u = G[v][id];
	if(max_dep[u][0].sc != rid[v][id])dep[v][id] = max_dep[u][0].fr+1;
	else dep[v][id] = max_dep[u][1].fr+1;
	cnt[v][id] = sum_cnt[u]-cnt[u][rid[v][id]]+(s_[u]?1:0);
	if(max_dep[v][1] < P(dep[v][id],id)){
		max_dep[v][1] = P(dep[v][id],id);
		if(max_dep[v][0] < max_dep[v][1])swap(max_dep[v][0],max_dep[v][1]);
	}
	sum_cnt[v] += cnt[v][id];
}
 
int main(){
	static int n;
	static int a[200010],b[200010];
	string s;
	scanf("%d",&n);
	rep1(i,n-1)scanf("%d%d",&a[i],&b[i]);
	cin >> s;
	
	rep1(i,n-1){
		rid[a[i]].pb(G[b[i]].size());
		rid[b[i]].pb(G[a[i]].size());
		G[a[i]].pb(b[i]);
		G[b[i]].pb(a[i]);
		dep[a[i]].pb(0);
		cnt[a[i]].pb(0);
		dep[b[i]].pb(0);
		cnt[b[i]].pb(0);
	}
	rep1(i,n){
		max_dep[i][0] = P(0,-1);
		max_dep[i][1] = P(0,-1);
		sum_cnt[i] = 0;
	}
	rep1(i,n){
		if(s[i-1] == '1')s_[i] = true;
		else s_[i] = false;
	}
	
	make_ord();
	for(P p: dp_ord){
		dfs(p.fr,p.sc);
	}
	
	ll ret = 0;
	rep1(i,n){
		vector<P> vec;
		rep(j,G[i].size()){
			vec.pb(P(dep[i][j],cnt[i][j]));
		}
		vec.pb(P(0,(s_[i]?1:0)));
		sor(vec);
		int d_max = vec[vec.size()-1].fr;
		int k = vec.size()-2;
		int I = 0;
		while(I+1 < vec.size() && vec[I].sc == 0)I ++;
		ret += max( min( d_max , vec[k].fr+2 ) - vec[I].fr , 0 );
	}
	cout << ret+1 << endl;
}
```