//waz
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;

#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))

int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}

const int N = 2e5 + 10;

VI edge[N];

char str[N];

int n, in[N], out[N], dfs_clock, fa[N], dep[N], d[N];

void dfs1(int u)
{
	in[u] = ++dfs_clock;
	for (auto v : edge[u])
	{
		if (v == fa[u]) continue;
		fa[v] = u;
		dep[v] = dep[u] + 1;
		dfs1(v);
	}
	out[u] = dfs_clock;
}

struct node
{
	int l, r;
	int val, tag;
	void add(int x) { val += x; tag += x; }
} t[N << 2];

void push_up(int o) { t[o].val = max(t[o << 1].val, t[o << 1 | 1].val); }

void push_down(int o)
{
	if (t[o].tag)
	{
		t[o << 1].add(t[o].tag);
		t[o << 1 | 1].add(t[o].tag);
		t[o].tag = 0;
	}
}

void build(int o, int l, int r)
{
	t[o].l = l, t[o].r = r;
	if (l == r)
	{
		t[o].val = d[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(o << 1, l, mid);
	build(o << 1 | 1, mid + 1, r);
	push_up(o);
}

int query(int o, int l, int r)
{
	if (t[o].r < l || r < t[o].l) return 0;
	if (l <= t[o].l && t[o].r <= r) return t[o].val;
	push_down(o);
	return max(query(o << 1, l, r), query(o << 1 | 1, l, r));
}

void add(int o, int l, int r, int x)
{
	if (t[o].r < l || r < t[o].l) return;
	if (l <= t[o].l && t[o].r <= r) return t[o].add(x);
	push_down(o);
	add(o << 1, l, r, x);
	add(o << 1 | 1, l, r, x);
	push_up(o);
}

/*
int pa[N];

int find(int x) { return x == pa[x] ? x : pa[x] = find(pa[x]); }

void unit(int x, int y)
{
	x = find(x), y = find(y);
	if (x == y) return;
	pa[x] = y; str[y] |= str[x];
}
*/

int mxt[N], mxa[N], mxb[N];

void dfs2(int u)
{
	int a = query(1, in[u], out[u]) + 1;
	int b = max(query(1, 1, in[u] - 1), query(1, out[u] + 1, n));
	if (fa[u]) mxt[u] = min(a + 1, b), mxa[u] = a + 1, mxb[u] = b; else mxt[u] = a; // >= t[u] : GG
	for (auto v : edge[u])
	{
		if (v == fa[u]) continue;
		add(1, in[v], out[v], -1);
		add(1, 1, in[v] - 1, 1);
		add(1, out[v] + 1, n, 1);
		dfs2(v);
		add(1, in[v], out[v], 1);
		add(1, 1, in[v] - 1, -1);
		add(1, out[v] + 1, n, -1);
	}
}

int64 ans;

int num[N];

void dfs3(int u)
{
	//cerr << u << ", " << mxt[u] << " : " << mxa[u] << ", " << mxb[u] << endl;
	for (auto v : edge[u])
	{
		if (v == fa[u]) continue;
		dfs3(v);
		if (mxt[v] > num[v]) ans += mxt[v] - num[v], num[u] = min(num[u], min(mxa[v] - 1, mxb[v] + 1));
		else num[u] = min(num[u], num[v]);
	}
}

int main()
{
	gi(n);
	for (int i = 1; i < n; ++i)
	{
		int u, v;
		gii(u, v);
		edge[u].pb(v);
		edge[v].pb(u);
	}
	scanf("%s", str + 1);
	for (int i = 1; i <= n; ++i) str[i] -= '0';
	for (int i = 1; i <= n; ++i) if (!str[i]) num[i] = N;
	int root = 1;
	for (; !str[root]; ++root);
	dfs1(root);
	for (int i = 1; i <= n; ++i) d[in[i]] = dep[i];
	build(1, 1, n);
	dfs2(root);
	dfs3(root);
	printf("%lld\n", ans + mxt[root]);
	return 0;
}
### Prompt

Create a solution in cpp for 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
//waz
#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)((x).size()))

typedef pair<int, int> PII;
typedef vector<int> VI;
typedef long long int64;
typedef unsigned int uint;
typedef unsigned long long uint64;

#define gi(x) ((x) = F())
#define gii(x, y) (gi(x), gi(y))
#define giii(x, y, z) (gii(x, y), gi(z))

int F()
{
	char ch;
	int x, a;
	while (ch = getchar(), (ch < '0' || ch > '9') && ch != '-');
	if (ch == '-') ch = getchar(), a = -1;
	else a = 1;
	x = ch - '0';
	while (ch = getchar(), ch >= '0' && ch <= '9')
		x = (x << 1) + (x << 3) + ch - '0';
	return a * x;
}

const int N = 2e5 + 10;

VI edge[N];

char str[N];

int n, in[N], out[N], dfs_clock, fa[N], dep[N], d[N];

void dfs1(int u)
{
	in[u] = ++dfs_clock;
	for (auto v : edge[u])
	{
		if (v == fa[u]) continue;
		fa[v] = u;
		dep[v] = dep[u] + 1;
		dfs1(v);
	}
	out[u] = dfs_clock;
}

struct node
{
	int l, r;
	int val, tag;
	void add(int x) { val += x; tag += x; }
} t[N << 2];

void push_up(int o) { t[o].val = max(t[o << 1].val, t[o << 1 | 1].val); }

void push_down(int o)
{
	if (t[o].tag)
	{
		t[o << 1].add(t[o].tag);
		t[o << 1 | 1].add(t[o].tag);
		t[o].tag = 0;
	}
}

void build(int o, int l, int r)
{
	t[o].l = l, t[o].r = r;
	if (l == r)
	{
		t[o].val = d[l];
		return;
	}
	int mid = (l + r) >> 1;
	build(o << 1, l, mid);
	build(o << 1 | 1, mid + 1, r);
	push_up(o);
}

int query(int o, int l, int r)
{
	if (t[o].r < l || r < t[o].l) return 0;
	if (l <= t[o].l && t[o].r <= r) return t[o].val;
	push_down(o);
	return max(query(o << 1, l, r), query(o << 1 | 1, l, r));
}

void add(int o, int l, int r, int x)
{
	if (t[o].r < l || r < t[o].l) return;
	if (l <= t[o].l && t[o].r <= r) return t[o].add(x);
	push_down(o);
	add(o << 1, l, r, x);
	add(o << 1 | 1, l, r, x);
	push_up(o);
}

/*
int pa[N];

int find(int x) { return x == pa[x] ? x : pa[x] = find(pa[x]); }

void unit(int x, int y)
{
	x = find(x), y = find(y);
	if (x == y) return;
	pa[x] = y; str[y] |= str[x];
}
*/

int mxt[N], mxa[N], mxb[N];

void dfs2(int u)
{
	int a = query(1, in[u], out[u]) + 1;
	int b = max(query(1, 1, in[u] - 1), query(1, out[u] + 1, n));
	if (fa[u]) mxt[u] = min(a + 1, b), mxa[u] = a + 1, mxb[u] = b; else mxt[u] = a; // >= t[u] : GG
	for (auto v : edge[u])
	{
		if (v == fa[u]) continue;
		add(1, in[v], out[v], -1);
		add(1, 1, in[v] - 1, 1);
		add(1, out[v] + 1, n, 1);
		dfs2(v);
		add(1, in[v], out[v], 1);
		add(1, 1, in[v] - 1, -1);
		add(1, out[v] + 1, n, -1);
	}
}

int64 ans;

int num[N];

void dfs3(int u)
{
	//cerr << u << ", " << mxt[u] << " : " << mxa[u] << ", " << mxb[u] << endl;
	for (auto v : edge[u])
	{
		if (v == fa[u]) continue;
		dfs3(v);
		if (mxt[v] > num[v]) ans += mxt[v] - num[v], num[u] = min(num[u], min(mxa[v] - 1, mxb[v] + 1));
		else num[u] = min(num[u], num[v]);
	}
}

int main()
{
	gi(n);
	for (int i = 1; i < n; ++i)
	{
		int u, v;
		gii(u, v);
		edge[u].pb(v);
		edge[v].pb(u);
	}
	scanf("%s", str + 1);
	for (int i = 1; i <= n; ++i) str[i] -= '0';
	for (int i = 1; i <= n; ++i) if (!str[i]) num[i] = N;
	int root = 1;
	for (; !str[root]; ++root);
	dfs1(root);
	for (int i = 1; i <= n; ++i) d[in[i]] = dep[i];
	build(1, 1, n);
	dfs2(root);
	dfs3(root);
	printf("%lld\n", ans + mxt[root]);
	return 0;
}
```