#include using namespace std; #define pb emplace_back #define mp make_pair using ll = long long; using pii = pair; constexpr int mod = 998244353; constexpr int inf = 0x3f3f3f3f; constexpr int N = 1e5 + 10; constexpr int M = 4e6 + 10; int n, val[N], tree[N], node_cnt, lch[M], rch[M], sum[M], buf_len, buf[M]; char s[N]; vector G[N]; vector V[N]; ll ans; int newnode(){ int o; if(buf_len){ o = buf[--buf_len]; } else { o = ++node_cnt; } lch[o] = rch[o] = 0; sum[o] = 0; return o; } void add(int &o, int L, int R, int p, int v){ if(!o) o = newnode(); sum[o] += v; if(L == R){ return; } int mid = (L + R) >> 1; if(p <= mid) add(lch[o], L, mid, p, v); else add(rch[o], mid + 1, R, p, v); } int query(int o, int L, int R, int l, int r){ if(!o) return 0; if(L == l && R == r) return sum[o]; int mid = (L + R) >> 1; if(r <= mid) return query(lch[o], L, mid, l, r); if(l > mid) return query(rch[o], mid + 1, R, l, r); return query(lch[o], L, mid, l, mid) + query(rch[o], mid + 1, R, mid + 1, r); } void walk(int o){ if(!o) return; walk(lch[o]); walk(rch[o]); buf[buf_len++] = o; } void join(int x, int y, int fa){ if(G[x].size() < G[y].size()){ swap(G[x], G[y]); swap(tree[x], tree[y]); } for(int v : G[y]){ int target = val[x] + val[fa] - v + 1; if(target <= N){ ans += query(tree[x], -N, N, max(target, -N), N); } G[x].pb(v); } for(int v : G[y]){ add(tree[x], -N, N, v, 1); } G[y].clear(); walk(tree[y]); } void dfs(int x, int fa){ if(s[x-1] == '1'){ val[x] = 1; ++ans; } else { val[x] = -1; } val[x] += val[fa]; tree[x] = newnode(); add(tree[x], -N, N, val[x], 1); G[x].pb(val[x]); for(int y : V[x]){ if(y == fa) continue; dfs(y, x); join(x, y, fa); } } void _main(){ int x, y; cin >> n; for(int i=1; i> x >> y; V[x].pb(y); V[y].pb(x); } cin >> s; val[0] = 0; dfs(1, 0); cout << ans << '\n'; } int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); _main(); return 0; }