#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}
struct Seg {
    bool fav;
    int height;
    Seg() { 
	fav = false;
	height = -1;
    }
    Seg inc(bool fav_) const {
	Seg z = *this;
	z.fav = z.fav || fav_;
	z.height++;
	return z;
    }
};
Seg operator+(const Seg &x, const Seg &y) {
    Seg z;
    z.fav = x.fav || y.fav;
    z.height = max(x.height, y.height);
    return z;
}

const int MAXN = 200111;
int N;
VI G[MAXN];
VI ord;
char S[MAXN];
Seg up[MAXN], dw[MAXN];
vector<Seg> L[MAXN], R[MAXN];

LL answer;

void treeDP() {
    ord.clear(); ord.reserve(N);
    ord.push_back(0);
    REP (i_, N) {
	int v = ord[i_];
	EACH (e, G[v]) {
	    ord.push_back(*e);
	    G[*e].erase(remove(G[*e].begin(), G[*e].end(), v), G[*e].end()); // remove parent
	}
    }

    REP (i_, N) {
	int v = ord[N-1-i_];
	int m = G[v].size();
	L[v].assign(m+1, Seg());
	R[v].assign(m+1, Seg());
	REP (i, m)
	    L[v][i+1] = L[v][i] + up[G[v][i]];
	for (int i=m; i--; )
	    R[v][i] = up[G[v][i]] + R[v][i+1];
	up[v] = R[v][0].inc(S[v] == '1'); // up[v] = L[v].all + v own
    }

    const int INF = 1<<29;

    dw[0] = Seg();
    REP (i_, N) {
	int v = ord[i_];
	//ans[v] = (R[v][0] + dw[v]).inc(S[v] == '1'); // when v == 0, dw[v] is an empty tree

	int lo = INF, hi[3] = { };
	auto update = [&](int h) {
	    hi[2] = h;
	    if (hi[1] < hi[2]) swap(hi[1], hi[2]);
	    if (hi[0] < hi[1]) swap(hi[0], hi[1]);
	};

	if (S[v] == '1') {
	    amin(lo, 0);
	}

	if (v) {
	    if (dw[v].fav) amin(lo, dw[v].height+1);
	    update(dw[v].height+1);

	    // dw[v] * up[v];
	    if (dw[v].height <= up[v].height && dw[v].fav) {
		answer++;
	    } else if (dw[v].height >= up[v].height && up[v].fav) {
		answer++;
	    }
	}

	REP (i, G[v].size()) {
	    int w = G[v][i];
	    if (up[w].fav) amin(lo, up[w].height+1);
	    update(up[w].height+1);
	}

	if (lo <= hi[1]) {
	    answer += hi[1] - lo + 1;
	}

	REP (i, G[v].size()) {
	    int w = G[v][i];
	    dw[w] = (R[v][i+1] + dw[v] + L[v][i]).inc(S[v] == '1'); // add v own
	}
    }
}



void MAIN() {
    scanf("%d", &N);
    REP (i, N-1) {
	int x, y;
	scanf("%d%d", &x, &y);
	x--; y--;
	G[x].push_back(y);
	G[y].push_back(x);
    }
    scanf("%s", S);
    treeDP();

    printf("%lld\n", answer);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}


### Prompt

Your challenge is to write 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<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<string.h>

#ifdef LOCAL
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define NDEBUG
#define eprintf(...) do {} while (0)
#endif
#include<cassert>

using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)

template<class T> inline void amin(T &x, const T &y) { if (y<x) x=y; }
template<class T> inline void amax(T &x, const T &y) { if (x<y) x=y; }
template<class Iter> void rprintf(const char *fmt, Iter begin, Iter end) {
    for (bool sp=0; begin!=end; ++begin) { if (sp) putchar(' '); else sp = true; printf(fmt, *begin); }
    putchar('\n');
}
struct Seg {
    bool fav;
    int height;
    Seg() { 
	fav = false;
	height = -1;
    }
    Seg inc(bool fav_) const {
	Seg z = *this;
	z.fav = z.fav || fav_;
	z.height++;
	return z;
    }
};
Seg operator+(const Seg &x, const Seg &y) {
    Seg z;
    z.fav = x.fav || y.fav;
    z.height = max(x.height, y.height);
    return z;
}

const int MAXN = 200111;
int N;
VI G[MAXN];
VI ord;
char S[MAXN];
Seg up[MAXN], dw[MAXN];
vector<Seg> L[MAXN], R[MAXN];

LL answer;

void treeDP() {
    ord.clear(); ord.reserve(N);
    ord.push_back(0);
    REP (i_, N) {
	int v = ord[i_];
	EACH (e, G[v]) {
	    ord.push_back(*e);
	    G[*e].erase(remove(G[*e].begin(), G[*e].end(), v), G[*e].end()); // remove parent
	}
    }

    REP (i_, N) {
	int v = ord[N-1-i_];
	int m = G[v].size();
	L[v].assign(m+1, Seg());
	R[v].assign(m+1, Seg());
	REP (i, m)
	    L[v][i+1] = L[v][i] + up[G[v][i]];
	for (int i=m; i--; )
	    R[v][i] = up[G[v][i]] + R[v][i+1];
	up[v] = R[v][0].inc(S[v] == '1'); // up[v] = L[v].all + v own
    }

    const int INF = 1<<29;

    dw[0] = Seg();
    REP (i_, N) {
	int v = ord[i_];
	//ans[v] = (R[v][0] + dw[v]).inc(S[v] == '1'); // when v == 0, dw[v] is an empty tree

	int lo = INF, hi[3] = { };
	auto update = [&](int h) {
	    hi[2] = h;
	    if (hi[1] < hi[2]) swap(hi[1], hi[2]);
	    if (hi[0] < hi[1]) swap(hi[0], hi[1]);
	};

	if (S[v] == '1') {
	    amin(lo, 0);
	}

	if (v) {
	    if (dw[v].fav) amin(lo, dw[v].height+1);
	    update(dw[v].height+1);

	    // dw[v] * up[v];
	    if (dw[v].height <= up[v].height && dw[v].fav) {
		answer++;
	    } else if (dw[v].height >= up[v].height && up[v].fav) {
		answer++;
	    }
	}

	REP (i, G[v].size()) {
	    int w = G[v][i];
	    if (up[w].fav) amin(lo, up[w].height+1);
	    update(up[w].height+1);
	}

	if (lo <= hi[1]) {
	    answer += hi[1] - lo + 1;
	}

	REP (i, G[v].size()) {
	    int w = G[v][i];
	    dw[w] = (R[v][i+1] + dw[v] + L[v][i]).inc(S[v] == '1'); // add v own
	}
    }
}



void MAIN() {
    scanf("%d", &N);
    REP (i, N-1) {
	int x, y;
	scanf("%d%d", &x, &y);
	x--; y--;
	G[x].push_back(y);
	G[y].push_back(x);
    }
    scanf("%s", S);
    treeDP();

    printf("%lld\n", answer);
}

int main() {
    int TC = 1;
//    scanf("%d", &TC);
    REP (tc, TC) MAIN();
    return 0;
}


```