/* #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") //*/ // #include #include using namespace std; // using namespace atcoder; // #define _GLIBCXX_DEBUG #define DEBUG(x) cerr << #x << ": " << x << endl; #define DEBUG_VEC(v) \ cerr << #v << ":"; \ for (int iiiiiiii = 0; iiiiiiii < v.size(); iiiiiiii++) \ cerr << " " << v[iiiiiiii]; \ cerr << endl; #define DEBUG_MAT(v) \ cerr << #v << endl; \ for (int iv = 0; iv < v.size(); iv++) { \ for (int jv = 0; jv < v[iv].size(); jv++) { \ cerr << v[iv][jv] << " "; \ } \ cerr << endl; \ } typedef long long ll; // #define int ll #define vi vector #define vl vector #define vii vector> #define vll vector> #define pii pair #define pis pair #define psi pair #define pll pair template pair operator+(const pair &s, const pair &t) { return pair(s.first + t.first, s.second + t.second); } template pair operator-(const pair &s, const pair &t) { return pair(s.first - t.first, s.second - t.second); } template ostream &operator<<(ostream &os, pair p) { os << "(" << p.first << ", " << p.second << ")"; return os; } #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define rep1(i, n) for (int i = 1; i <= (int)(n); i++) #define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; i--) #define rrep1(i, n) for (int i = (int)(n); i > 0; i--) #define REP(i, a, b) for (int i = a; i < b; i++) #define in(x, a, b) (a <= x && x < b) #define all(c) c.begin(), c.end() void YES(bool t = true) { cout << (t ? "YES" : "NO") << endl; } void Yes(bool t = true) { cout << (t ? "Yes" : "No") << endl; } void yes(bool t = true) { cout << (t ? "yes" : "no") << endl; } void NO(bool t = true) { cout << (t ? "NO" : "YES") << endl; } void No(bool t = true) { cout << (t ? "No" : "Yes") << endl; } void no(bool t = true) { cout << (t ? "no" : "yes") << endl; } template bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template bool chmin(T &a, const T &b) { if (a > b) { a = b; return 1; } return 0; } template T ceil_div(T a, U b) { return (a + b - 1) / b; } template T safe_mul(T a, T b) { if (a == 0 || b == 0) return 0; if (numeric_limits::max() / a < b) return numeric_limits::max(); return a * b; } #define UNIQUE(v) v.erase(std::unique(v.begin(), v.end()), v.end()); const ll inf = 1000000001; const ll INF = (ll)1e18 + 1; const long double pi = 3.1415926535897932384626433832795028841971L; int popcount(ll t) { return __builtin_popcountll(t); } vector gen_perm(int n) { vector ret(n); iota(all(ret), 0); return ret; } // int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; // int dx2[8] = { 1,1,0,-1,-1,-1,0,1 }, dy2[8] = { 0,1,1,1,0,-1,-1,-1 }; vi dx = {0, 0, -1, 1}, dy = {-1, 1, 0, 0}; vi dx2 = {1, 1, 0, -1, -1, -1, 0, 1}, dy2 = {0, 1, 1, 1, 0, -1, -1, -1}; struct Setup_io { Setup_io() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); cout << fixed << setprecision(25); cerr << fixed << setprecision(25); } } setup_io; // constexpr ll MOD = 1000000007; constexpr ll MOD = 998244353; // #define mp make_pair struct DSUOnTree { // https://nyaannyaan.github.io/library/tree/dsu-on-tree.hpp.html // https://codeforces.com/blog/entry/44351 vector> G; int n; // 頂点 u の部分木は ord の [from[u], to[u]) の範囲に入っている vector sub, ord, from, to; int root; int dfs_sub(int now, int par) { sub[now] = 1; if (G[now].size() >= 2 && G[now][0] == par) { // 最初の子は Big Child になるようにする swap(G[now][0], G[now][1]); } for (int i = 0; i < G[now].size(); i++) { int to = G[now][i]; if (to == par) continue; sub[now] += dfs_sub(to, now); if (i != 0 && sub[G[now][0]] < sub[to]) { swap(G[now][0], G[now][i]); } } return sub[now]; } void dfs_ord(int now, int par, int &idx) { from[now] = idx; ord[idx++] = now; for (int to : G[now]) { if (to == par) continue; dfs_ord(to, now, idx); } to[now] = idx; } public: DSUOnTree(vector> G, int root) : G(G), n(G.size()), root(root) { sub.resize(n); from.resize(n); to.resize(n); ord.reserve(n); dfs_sub(root, -1); int idx = 0; dfs_ord(root, -1, idx); } using F = function; void run(F update, F query, F clear) { // 各関数を通じて、外部に用意した配列やセグ木にアクセスする想定 // update(u): 頂点 u 単体に関して値を更新する // query(u): 頂点 u が属する部分木に関しての更新が終わった状態でクエリを処理する // clear(u): 頂点 u 単体に関しての更新を解除する // verify: https://judge.yosupo.jp/submission/235963 auto dfs = [&](auto &&self, int now, int par, bool keep) -> void { // dfs Small Child for (int i = 1; i < G[now].size(); i++) { if (G[now][i] == par) continue; self(self, G[now][i], now, false); } // dfs Big Child if (sub[now] > 1) { self(self, G[now][0], now, true); } // update Small Child if (sub[now] > 1) { int bc = G[now][0]; for (int i = to[bc]; i < to[now]; i++) { update(ord[i]); } } update(now); query(now); if (!keep) { for (int i = from[now]; i < to[now]; i++) { clear(ord[i]); } } return; }; dfs(dfs, root, -1, true); } using F2 = function; void run_every_pair(F update, F query_root, F2 query_light, F clear) { // 各関数を通じて、外部に用意した配列やセグ木にアクセスする想定。 // 全ての異なる頂点ペアに関するクエリを処理する。同じ頂点ペアに関するクエリがある場合は別途処理する必要がある。 // update(u): 頂点 u 単体に関して値を更新する // query_root(u): 頂点 u を根として追加する時に、u とその子孫に関するクエリを処理する。 // query_light(r, u): 頂点 r が根の時に頂点 u を Small Child として追加する時に、 // u と「r の Big Child, および r の処理済みの Small Child」に関するクエリを処理する。 // u と r に関するクエリは query_root で処理されるので、ここでは扱わない // clear(u): 頂点 u 単体に関しての更新を解除する auto dfs = [&](auto &&self, int now, int par, bool keep) -> void { // dfs Small Child for (int i = 1; i < G[now].size(); i++) { if (G[now][i] == par) continue; self(self, G[now][i], now, false); } // dfs Big Child if (sub[now] > 1) { self(self, G[now][0], now, true); } // update Small Child if (sub[now] > 1) { for (int i = 1; i < G[now].size(); i++) { if (G[now][i] == par) continue; int ch = G[now][i]; // Big Child とすでに処理済みの Small Child に関するクエリを処理 for (int u = from[ch]; u < to[ch]; u++) { query_light(now, ord[u]); } for (int u = from[ch]; u < to[ch]; u++) { update(ord[u]); } } } // 根と子孫の間のクエリを処理 query_root(now); update(now); if (!keep) { for (int i = from[now]; i < to[now]; i++) { clear(ord[i]); } } return; }; dfs(dfs, root, -1, true); } }; class Bit { public: int n; vl bit; // 0-index Bit(int _n) { n = _n; bit.resize(n); } // [0, i) ll sum(int i) { ll s = 0; while (i > 0) { s += bit[i - 1]; i -= i & -i; } return s; } // [l, r) ll sum(int l, int r) { if (l >= r) return 0; return sum(r) - sum(l); } void add(int i, ll x) { i++; while (i <= n) { bit[i - 1] += x; i += i & -i; } } ll min_xth(int x) { // なぜか 1-indexed // x = 0 の時は必ず 0 が返っていそう int left = -1, right = n; while (left + 1 < right) { int mid = (left + right) / 2; int temp = sum(mid + 1); if (temp < x) { left = mid; } else { right = mid; } } return right; } ll bubble(vi p) { int n = p.size(); ll ans = 0; for (int j = 0; j < n; j++) { ans += (j - sum(p[j] + 1)); add(p[j], 1); } return ans; } }; signed main() { int n; cin >> n; vii G(n); rep(i, n - 1) { int u, v; cin >> u >> v; u--; v--; G[u].push_back(v); G[v].push_back(u); } string s; cin >> s; vi a(n); rep(i, n) { if (s[i] == '1') a[i] = 1; else a[i] = -1; } vi rui(n); auto dfs_rui = [&](auto &&f, int now, int par, int d) -> void { rui[now] = d + a[now]; for (int to : G[now]) { if (to == par) continue; f(f, to, now, rui[now]); } }; dfs_rui(dfs_rui, 0, -1, 0); int OFF = n; Bit bit(2 * n + 1); ll ans = 0; auto update = [&](int u) { bit.add(rui[u] + OFF, 1); }; auto query_root = [&](int u) { // DEBUG(u); // for (int i = -n; i <= n; i++) { // DEBUG(pii(i, bit.sum(i + OFF, i + 1 + OFF))); // } int p = rui[u] - a[u]; // x - p > 0 // x > p ans += bit.sum(p + 1 + OFF, 2 * n + 1); }; auto query_light = [&](int r, int u) { int p = rui[r] - a[r]; int val1 = rui[u] - p; // val1 + x - p - a[r] > 0 // x > p + a[r] - val1 ans += bit.sum(p + a[r] - val1 + 1 + OFF, 2 * n + 1); }; auto clear = [&](int u) { bit.add(rui[u] + OFF, -1); }; DSUOnTree dsu(G, 0); dsu.run_every_pair(update, query_root, query_light, clear); rep(i, n) { if (a[i] == 1) ans++; } cout << ans << endl; }