#include // #include // #include using namespace std; // using namespace atcoder; // using bint = boost::multiprecision::cpp_int; using ll = long long; using ull = unsigned long long; using ld = long double; using P = pair; using vi = vector; using vvi = vector; using vvvi = vector; using ve = vector>; using vb = vector; using vvb = vector; #define rep(i,n) for(ll i = 0;i < (ll)n;i++) #define ALL(x) (x).begin(),(x).end() #define sz(c) ((ll)(c).size()) #define LB(A,x) (int)(lower_bound(A.begin(),A.end(),x)-A.begin()) #define UB(A,x) (int)(upper_bound(A.begin(),A.end(),x)-A.begin()) // #define MOD 1000000007 #define MOD 998244353 templateusing min_priority_queue=priority_queue,greater>; templateostream&operator<<(ostream&os,vector&v){for(int i = 0;i < v.size();i++)os<istream&operator>>(istream&is,vector&v){for(T&in:v)is>>in;return is;} templateostream&operator<<(ostream&os,pair&p){os<istream&operator>>(istream&is,pair&p){is>>p.first>>p.second;return is;} template inline bool chmax(T &a,T b){if(a < b){a = b;return true;}return false;} template inline bool chmin(T &a,T b){if(a > b){a = b;return true;}return false;} ld dist(ld x1,ld y1,ld x2, ld y2){return sqrtl((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));} // verifiy // 重心分解 https://atcoder.jp/contests/abc291/submissions/54751516 // 分割統治 https://atcoder.jp/contests/ddcc2016-qual/submissions/54751335 struct edge{ int to; // 情報を追加 // ll we; // edge(int a,ll b):to(a),we(b){} edge(int k):to(k){} }; using vve = vector>; struct CD{ int n; vector> v; vector used_centroid; vector sub_sz;//内部用。重心分解の各段階で計算する部分木の大きさ vector par;//重心分解後の親の頂点 CD(vector> &a) : n((int)a.size()),v(a),used_centroid(a.size(),false),sub_sz(a.size(),1),par(a.size(),-1){} int subtree_sz(int ov,int pre){ int res = 1; for(int i = 0;i < (int)v[ov].size();i++){ int to = v[ov][i].to; if(to == pre || used_centroid[to])continue; res += subtree_sz(to,ov); } sub_sz[ov] = res; return res; } int get_centroid(int ov,int now_sz){ while(1){ int mx = -1,can_v = -1; for(auto nv : v[ov]){ // 重心でない / 逆走しない 条件 if(used_centroid[nv.to] || sub_sz[nv.to] > sub_sz[ov])continue; mx = max(mx,sub_sz[nv.to]); if(mx == sub_sz[nv.to])can_v = nv.to; } if(mx <= now_sz/2)break; ov = can_v; } return ov; } // ovが所属する部分木に対する重心分解 // 使うときはpre = -1を入れる // O(nlogn) void cd(int ov,int pre,string &s,ll &res){//分割統治に必要なら引数を増やす subtree_sz(ov,-1); ov = get_centroid(ov,sub_sz[ov]); par[ov] = pre; used_centroid[ov] = true; vi ds;ds.emplace_back(0); // /* // 重心ovに対して➀u->ov->v ➁ov->u となる頂点対に対する部分問題を書く。必要ならば下のdfsを用いる auto count = [](vi &d,string &s,int ov){ sort(ALL(d)); ll res = 0; rep(i,sz(d)){ int k = LB(d,-((s[ov] == '1' ? 1 : -1) + d[i])+1); res += sz(d)-k; } return res; }; rep(i,sz(v[ov])){ int to = v[ov][i].to; if(used_centroid[to])continue; vi dt; auto dfs = [&](auto &dfs,int OV,int PRE,ll cnt)->void{ dt.emplace_back(cnt + (s[OV] == '1' ? 1 : -1)); for(auto nv : v[OV]){ if(nv.to == PRE || used_centroid[nv.to])continue; dfs(dfs,nv.to,OV,cnt + (s[OV] == '1' ? 1 : -1)); } }; dfs(dfs,v[ov][i].to,ov,0); ll we = count(dt,s,ov); res -= we; ds.insert(ds.end(),ALL(dt)); } ll we = count(ds,s,ov); res += we; if(s[ov] == '1')res++; for(int i = 0;i < (int)v[ov].size();i++){ if(used_centroid[v[ov][i].to])continue; cd(v[ov][i].to,ov,s,res); } } }; int main(){ ios_base::sync_with_stdio(0), cin.tie(0); int n; cin >> n; vve v(n); rep(i,n-1){ int a,b;cin >> a >> b; a--;b--; v[a].emplace_back((edge)(b)); v[b].emplace_back((edge)(a)); } CD cd(v); string s;cin >> s; ll res = 0; cd.cd(0,-1,s,res); res /= 2; cout << res << "\n"; return 0; }