#include using namespace std; using ll = long long; template using vec = vector; template using vv = vec>; template using vvv = vec>; using vl = vec; using vvl = vv; #define rep(i, n) for (ll i = 0; i < ll(n); i++) #define eb emplace_back #include using namespace atcoder; ll op(ll a, ll b) { return a + b; } ll e() { return 0; } void solve() { ll n; cin >> n; vvl g(n); rep(i, n - 1) { ll u, v; cin >> u >> v; u--, v--; g[u].eb(v); g[v].eb(u); } string s; cin >> s; vl bfs; bfs.reserve(n); vl par(n, -1), sz(n, 1), depth(n, 0); vvl child(n); { queue q({0}); while (q.size() > 0) { ll now = q.front(); q.pop(); bfs.eb(now); for (auto to : g[now]) { if (par[now] == to) continue; par[to] = now; q.push(to); } } } for (auto now : bfs | views::reverse) { for (auto to : g[now]) { if (par[now] == to) continue; sz[now] += sz[to]; depth[now] = max(depth[now], depth[to] + 1); child[now].eb(to); if (sz[child[now][0]] < sz[child[now].back()]) swap(child[now][0], child[now].back()); } } // rep(now, n) cout << sz[now] << " "; // cout << "\n"; using SEG = segtree; ll ans = 0; auto dfs = [&](auto f, ll now) -> tuple { ll cur = now; ll seg_sz = 2 * sz[now] + 3; SEG seg(seg_sz); ll diff = sz[now] + 1; while (child[cur].size() > 0) cur = child[cur][0]; while (true) { seg.set(diff, seg.get(diff) + 1); if (s[cur] == '0') diff--; else diff++; // if (seg.prod(0, diff) > 0) // cout << cur << ", + " << seg.prod(0, diff) << "\n"; ans += seg.prod(0, diff); for (ll i = 1; i < child[cur].size(); i++) { ll to = child[cur][i]; auto [c_diff, c_seg, c_seg_sz] = f(f, to); for (ll j = 0; j < c_seg_sz; j++) { ll c_idx = j - c_diff; ll idx = diff - c_idx; ll tmp = seg.prod(0, idx) * c_seg.get(j); ans += tmp; // if (tmp > 0) cout << cur << ", " << to << ", + " << tmp << "\n"; } for (ll j = 0; j < c_seg_sz; j++) { ll c_idx = j - c_diff; ll idx = c_idx + diff; if (s[cur] == '0') idx++; else idx--; if (idx < 0 || seg_sz <= idx) continue; ll tmp = c_seg.get(j); if (tmp == 0) continue; tmp += seg.get(idx); seg.set(idx, tmp); } // cout << "cur, diff: " << cur << " " << diff << "\n"; // rep(i, diff) cout << seg.get(i) << " |"[i + 1 == diff]; // cout << seg.get(diff) << "|"; // for (ll i = diff + 1; i < seg_sz; i++) cout << seg.get(i) << " "; // cout << "\n"; } // if (child[cur].size() <= 1) { // cout << "cur, diff: " << cur << " " << diff << "\n"; // rep(i, diff) cout << seg.get(i) << " |"[i + 1 == diff]; // cout << seg.get(diff) << "|"; // for (ll i = diff + 1; i < seg_sz; i++) cout << seg.get(i) << " "; // cout << "\n"; // } if (cur == now) return {diff, seg, seg_sz}; cur = par[cur]; } }; dfs(dfs, 0); cout << ans << "\n"; } int main() { ll t = 1; // cin >> t; rep(i, t) solve(); }