#include #include using namespace std; using ll = long long; int main() { int n; cin >> n; vector g(n, vector()); for (size_t i=0; i> u >> v; u--; v--; g[u].push_back(v); g[v].push_back(u); } string s; cin >> s; vector t(n); for (size_t i=0; i fw(2*n+1); // -n..n ll ans = 0; vector sz(n, 1); vector heavy_child(n, -1); auto calc_sz = [&] (auto self, int u, int p) -> int { sz[u] = 1; for (auto x : g[u]) { if (x == p) continue; sz[u] += self(self, x, u); } int mx = -1; for (auto x : g[u]) { if (x == p) continue; if (mx < sz[x]) { mx = sz[x]; heavy_child[u] = x; } } return sz[u]; }; calc_sz(calc_sz, 0, -1); auto add = [&] (auto self, int u, int p, int val) -> void { fw.add(n+val+t[u], 1); for (auto x : g[u]) { if (x == p) continue; self(self, x, u, val+t[u]); } }; auto calc = [&] (auto self, int u, int p, int val, int base, int tu) -> void { int q = 2 * base - (val + t[u]); if (tu == -1) q += 2; ans += fw.sum(min(2*n+1, n+q), 2*n+1); for (auto x : g[u]) { if (x == p) continue; self(self, x, u, val+t[u], base, tu); } }; auto reset = [&] (auto self, int u, int p, int val) -> void { fw.add(n+val+t[u], -1); int add = (s[u] == '1' ? 1 : -1); for (auto x : g[u]) { if (x == p) continue; self(self, x, u, val+t[u]); } }; auto dfs = [&] (auto self, int u, int p, bool keep, int val) -> void { for (auto x : g[u]) { if (x == p || x == heavy_child[u]) continue; self(self, x, u, false, val+t[u]); } if (heavy_child[u] != -1) { self(self, heavy_child[u], u, true, val+t[u]); } for (auto x : g[u]) { if (x == p || x == heavy_child[u]) continue; calc(calc, x, u, val+t[u], val+t[u], t[u]); add(add, x, u, val+t[u]); } fw.add(n+val+t[u], 1); ans += fw.sum(n+val+1, 2*n+1); if (!keep) { reset(reset, u, p, val); } }; dfs(dfs, 0, -1, true, 0); cout << ans << endl; }