#pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using namespace atcoder; typedef long long ll; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define repr(i, n) for (int i = (int)(n) - 1; i >= 0; i--) #define repk(i, k, n) for (int i = k; i < (int)(n); i++) #define all(v) v.begin(), v.end() #define mod1 1000000007 #define mod2 998244353 #define mod3 100000007 #define vi vector #define vs vector #define vc vector #define vl vector #define vb vector #define vvi vector> #define vvc vector> #define vvl vector> #define vvb vector> #define vvvi vector>> #define vvvl vector>> #define pii pair #define pil pair #define pli pair #define pll pair #define vpii vector> #define vpll vector> #define vvpii vector>> #define vvpll vector>> using mint = modint998244353; template void debug(T e) { cerr << e << endl; } template void debug(vector &v) { rep(i, v.size()) { cerr << v[i] << " "; } cerr << endl; } template void debug(vector> &v) { rep(i, v.size()) { rep(j, v[i].size()) { cerr << v[i][j] << " "; } cerr << endl; } } template void debug(vector> &v) { rep(i, v.size()) { cerr << v[i].first << " " << v[i].second << endl; } } template void debug(set &st) { for (auto itr = st.begin(); itr != st.end(); itr++) { cerr << *itr << " "; } cerr << endl; } template void debug(multiset &ms) { for (auto itr = ms.begin(); itr != ms.end(); itr++) { cerr << *itr << " "; } cerr << endl; } template void debug(map &mp) { for (auto itr = mp.begin(); itr != mp.end(); itr++) { cerr << itr->first << " " << itr->second << endl; } } void debug_out() { cerr << endl; } template void debug_out(Head H, Tail... T) { cerr << H << " "; debug_out(T...); } struct centroid_decomposition { vector> graph; vector subtreesize; vector isremoved; vector parent; vector centroids; centroid_decomposition(vector &U, vector &V, ll N) { graph.resize(N); for (ll i = 0; i < N - 1; i++) { graph[U[i]].push_back(V[i]); graph[V[i]].push_back(U[i]); } subtreesize.assign(N, 0); isremoved.assign(N, false); parent.resize(N); } void calc_size(ll v, ll p) { subtreesize[v] = 1; for (ll x : graph[v]) { if (x == p) { continue; } if (isremoved[x]) { continue; } calc_size(x, v); subtreesize[v] += subtreesize[x]; } } void find(ll v, ll p) { calc_size(v, p); ll size = subtreesize[v]; ll pp = -1; ll now = v; while (true) { bool cont = false; for (ll x : graph[now]) { if (!isremoved[x] && x != pp && subtreesize[x] > size / 2) { cont = true; pp = now; now = x; cont = true; break; } } if (!cont) { break; } } parent[now] = p; isremoved[now] = true; centroids.push_back(now); for (ll x : graph[now]) { if (!isremoved[x]) { find(x, now); } } } vector make_centroids() { find(0, -1); return centroids; } vector print_parent() { return parent; } }; int main() { ll N; cin >> N; vector u(N - 1); vector v(N - 1); for (ll i = 0; i < N - 1; i++) { cin >> u[i] >> v[i]; u[i]--; v[i]--; } string S; cin >> S; centroid_decomposition CD(u, v, N); vector centroids = CD.make_centroids(); // debug(centroids); vector> graph(N, vector(0)); for (ll i = 0; i < N - 1; i++) { graph[u[i]].push_back(v[i]); graph[v[i]].push_back(u[i]); } vector used(N, false); vector dist(N, -1); vector prev(N, -1); ll ans = 0; for (ll i = 0; i < N; i++) { ll root = centroids[i]; used[root] = true; vector> vecs(0, vector(0)); vector minus_mins(0); queue que; for (ll j = 0; j < graph[root].size(); j++) { if (used[graph[root][j]]) { continue; } vector vecs_sub(0); ll minus_sub = 1; if (S[graph[root][j]] == '1') { dist[graph[root][j]] = 1; } else { dist[graph[root][j]] = -1; } vecs_sub.push_back(dist[graph[root][j]]); minus_sub = min(minus_sub, dist[graph[root][j]]); que.push(graph[root][j]); prev[graph[root][j]] = root; while (que.size()) { ll p = que.front(); que.pop(); for (ll x : graph[p]) { if (used[x]) { continue; } if (x == prev[p]) { continue; } if (S[x] == '1') { dist[x] = dist[p] + 1; } else { dist[x] = dist[p] - 1; } minus_sub = min(minus_sub, dist[x]); vecs_sub.push_back(dist[x]); que.push(x); prev[x] = p; } } vecs.push_back(vecs_sub); minus_mins.push_back(minus_sub); } // 定数部分の答えも探す if (S[root] == '1') { ans++; } for (ll j = 0; j < vecs.size(); j++) { for (ll k = 0; k < vecs[j].size(); k++) { if (S[root] == '1') { if (vecs[j][k] >= 0) { ans++; } } else { if (vecs[j][k] >= 2) { ans++; } } } } // debug(vecs); if (vecs.size() == 0) { continue; } // debug(vecs); // debug(minus_mins); // cout << endl; ll minus_min = 2; ll plus_max = -2; for (ll j = 0; j < vecs.size(); j++) { for (ll k = 0; k < vecs[j].size(); k++) { minus_min = min(minus_min, vecs[j][k]); plus_max = max(plus_max, vecs[j][k]); } } // debug_out(plus_max, minus_min); vector all_vec(plus_max - minus_min + 1, 0); for (ll j = 0; j < vecs.size(); j++) { for (ll k = 0; k < vecs[j].size(); k++) { all_vec[vecs[j][k] - minus_min]++; } } // debug(all_vec); vector sq_all = convolution_ll(all_vec, all_vec); // debug(sq_all); for (ll j = 0; j < vecs.size(); j++) { ll plus_sub = -1; ll minus_sub = 1; for (ll k = 0; k < vecs[j].size(); k++) { plus_sub = max(plus_sub, vecs[j][k]); minus_sub = min(minus_sub, vecs[j][k]); } vector sub_vec(plus_sub - minus_sub + 1); for (ll k = 0; k < vecs[j].size(); k++) { sub_vec[vecs[j][k] - minus_sub]++; } vector sq_sub = convolution_ll(sub_vec, sub_vec); for (ll k = 0; k < sq_sub.size(); k++) { sq_all[(minus_sub - minus_min) * 2 + k] -= sq_sub[k]; } } // debug(sq_all); // debug(minus_min); ll dline = -1; if (S[root] == '0') { dline = 1; } if (-minus_min * 2 + dline + 1 >= 0) { for (ll j = -minus_min * 2 + dline + 1; j < sq_all.size(); j++) { ans += sq_all[j] / 2; } } else { for (ll j = 0; j < sq_all.size(); j++) { ans += sq_all[j] / 2; } } // cout << ans << endl; } // cout << endl; cout << ans << endl; }