#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #ifdef LOCAL # include "debug_print.hpp" # define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else # define debug(...) (static_cast(0)) #endif using namespace std; #define rep1(a) for(int i = 0; i < a; i++) #define rep2(i, a) for(int i = 0; i < a; i++) #define rep3(i, a, b) for(int i = a; i < b; i++) #define rep4(i, a, b, c) for(int i = a; i < b; i += c) #define overload4(a, b, c, d, e, ...) e #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) #define rrep1(a) for(int i = (a)-1; i >= 0; i--) #define rrep2(i, a) for(int i = (a)-1; i >= 0; i--) #define rrep3(i, a, b) for(int i = (b)-1; i >= a; i--) #define rrep4(i, a, b, c) for(int i = (b)-1; i >= a; i -= c) #define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__) #define ALL(v) v.begin(), v.end() #define RALL(v) v.rbegin(), v.rend() #define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ); #define pb push_back using ll = long long; using D = double; using LD = long double; using P = pair; using vi = vector; using vl = vector; template using vc = vector; template using vvc = vector>; template using vvvc = vector>; template using vvvvc = vector>; template using vvvvvc = vector>; #define vv(type, name, h, ...) \ vector> name(h, vector(__VA_ARGS__)) #define vvv(type, name, h, w, ...) \ vector>> name( \ h, vector>(w, vector(__VA_ARGS__))) #define vvvv(type, name, a, b, c, ...) \ vector>>> name( \ a, vector>>( \ b, vector>(c, vector(__VA_ARGS__)))) template using PQ = priority_queue>; template using minPQ = priority_queue, greater>; templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b ostream &operator<<(ostream &os, const pair &p) { os << p.first << " " << p.second; return os; } template istream &operator>>(istream &is, pair &p) { is >> p.first >> p.second; return is; } template ostream &operator<<(ostream &os, const vector &v) { int s = (int)v.size(); for (int i = 0; i < s; i++) os << (i ? " " : "") << v[i]; return os; } template istream &operator>>(istream &is, vector &v) { for (auto &x : v) is >> x; return is; } void in() {} template void in(T &t, U &...u) { cin >> t; in(u...); } void out() { cout << "\n"; } template void out(const T &t, const U &...u) { cout << t; if (sizeof...(u)) cout << sep; out(u...); } void outr() {} template void outr(const T &t, const U &...u) { cout << t; outr(u...); } string s; int f[101010]; int freqf[202020]; int maxf = -101010, minf = 101010; ll ans = 0; struct CentroidDecomposition { int n; const vector> &g; vector sz, par; vector removed; CentroidDecomposition(const vector> &g) : n(g.size()), g(g), sz(g.size(), 0), par(g.size(), -1), removed(g.size(), false) {} void calcSubtreeSize(int u, int p) { sz[u] = 1; for (int v : g[u]) { if (!removed[v] and v != p) { calcSubtreeSize(v, u); sz[u] += sz[v]; } } } void calcF(int u, int p) { f[u] += (s[u] == '1' ? 1 : -1); freqf[f[u]+n]++; chmax(maxf, f[u]); chmin(minf, f[u]); for (int v : g[u]) { if (!removed[v] and v != p) { f[v] = f[u]; calcF(v, u); } } } void clearF(int u, int p) { f[u] = 0; for (int v : g[u]) { if (!removed[v] and v != p) { clearF(v, u); } } } void build(int u, int p) { calcSubtreeSize(u, -1); int sz_root = sz[u]; bool found = false; int pr = -1; while (!found) { found = true; for (int v : g[u]) { if (!removed[v] and v != pr and 2*sz[v] > sz_root) { pr = u, u = v, found = false; break; } } } par[u] = p; maxf = -101010, minf = 101010; f[u] = 0; calcF(u, -1); ll cs = 0; rep(i,f[u]-minf+1, maxf+1) cs += freqf[i+n]; rep(i,minf,maxf+1){ ans += freqf[i+n] * cs; cs += freqf[f[u]-i+n]; if(i*2 > f[u]) { ans -= (ll)freqf[i+n] * freqf[i+n]; ans += (ll)freqf[i+n] * (freqf[i+n]-1); } } rep(i,minf,maxf+1) freqf[i+n] = 0; for(int v : g[u]) if(!removed[v]){ maxf = -101010, minf = 101010; cs = 0; f[v] = 0; calcF(v, u); rep(i,f[v]-minf+1, maxf+1) cs += freqf[i+n]; rep(i,minf,maxf+1){ ans -= freqf[i+n] * cs; cs += freqf[f[v]-i+n]; if(i*2 > f[v]) { ans += (ll)freqf[i+n] * freqf[i+n]; ans -= (ll)freqf[i+n] * (freqf[i+n]-1); } } rep(i,minf,maxf+1) freqf[i+n] = 0; } removed[u] = true; for (int v : g[u]) if (!removed[v]) build(v, u); } }; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n; in(n); vector> g(n); rep(i,n-1){ int u,v; in(u,v); u--; v--; g[u].push_back(v); g[v].push_back(u); } in(s); CentroidDecomposition cd(g); cd.build(0,-1); ans /= 2; rep(i,n) if(s[i] == '1') ans++; out(ans); }