#include using namespace std; using SS = int; class SegmentTree{ public: int siz = 1,n; vector dat; SS op(SS a, SS b){return a+b;} SS e(){return 0;} void renew (SS &a,SS x){ a = op(a,x); //a = x; //その他. } void make(int N){ while(siz < N) siz *= 2; n = N; dat.resize(siz*2,e()); } void make2(int N,vector &A){ make(N); for(int i=0; i0; i--) dat.at(i) = op(dat.at(i*2),dat.at(i*2+1)); } void update(int pos,SS x){ pos = pos+siz; renew(dat.at(pos),x); while(pos != 1){ pos = pos/2; dat.at(pos) = op(dat.at(pos*2),dat.at(pos*2+1)); } } SS findans(int l, int r){ SS retl = e(),retr = e(); l += siz,r += siz; while(l < r){ if(l&1) retl = op(retl,dat.at(l++)); if(r&1) retr = op(dat.at(--r),retr); l >>= 1; r >>= 1; } return op(retl,retr); } SS get(int pos){return dat.at(pos+siz);} SS rangeans(int l, int r){return findans(l,r);} SS allrange(){return dat.at(1);} //rightは) leftは[で 渡す&返す. int maxright(const function f,int l = 0){ l += siz; int r = n+siz; vector ls,rs; while(l < r){ if(l&1) ls.push_back(l++); if(r&1) rs.push_back(--r); l >>= 1; r >>= 1; } SS okl = e(); for(int i=0; i=0; i--){ l = rs.at(i); SS now = op(okl,dat.at(l)); if(!f(now)){ while(l < siz){ l <<= 1; now = op(okl,dat.at(l)); if(f(now)){okl = now; l++;} } return l-siz; } okl = now; } return n; } int minleft(const function f,int r = -1){ if(r == -1) r = n; int l = siz; r += siz; vector ls,rs; while(l < r){ if(l&1) ls.push_back(l++); if(r&1) rs.push_back(--r); l >>= 1; r >>= 1; } SS okr = e(); for(int i=0; i=0; i--){ r = ls.at(i); SS now = op(dat.at(r),okr); if(!f(now)){ while(r < siz){ r <<= 1; r++; now = op(dat.at(r),okr); if(f(now)){okr = now; r--;} } return r+1-siz; } } return 0; } //ノーマルセグ木.一年の時を経て漸く二分探索実装した. }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector> Graph(N); for(int i=0; i> u >> v; u--; v--; Graph.at(u).push_back(v); Graph.at(v).push_back(u); } vector siz(N); { auto dfs = [&](auto dfs,int pos,int back) -> int { int ret = 1; for(auto to : Graph.at(pos)) if(to != back) ret += dfs(dfs,to,pos); siz.at(pos) = ret; return ret; }; dfs(dfs,0,-1); } for(auto &g : Graph) sort(g.begin(),g.end(),[&](auto &a,auto &b){return siz.at(a)>siz.at(b);}); SegmentTree Z; Z.make(N*2+9); int zero = N+4; long long answer = 0; string s; cin >> s; auto dfs = [&](auto dfs,int pos,int back) -> int { int maxs = 0,big = -1; for(auto to : Graph.at(pos)) if(to != back && maxs < siz.at(to)) maxs = siz.at(to),big = to; for(auto to : Graph.at(pos)){ if(to == back || to == big) continue; int n = dfs(dfs,to,pos); auto dfs2 = [&](auto dfs2,int pos,int back) -> void { if(s.at(pos) == '1') n++; else n--; Z.update(n,-1); for(auto to : Graph.at(pos)) if(to != back) dfs2(dfs2,to,pos); if(s.at(pos) == '1') n--; else n++; }; dfs2(dfs2,to,pos); } { int n = zero; if(big != -1) n = dfs(dfs,big,pos); Z.update(n,1); if(s.at(pos) == '1') n--; else n++; answer += Z.rangeans(n+1,Z.siz); auto dfs2 = [&](auto dfs2,int pos,int back) -> void { if(s.at(pos) == '1') n--; else n++; answer += Z.rangeans(n+1,Z.siz); for(auto to : Graph.at(pos)) if(to != back) dfs2(dfs2,to,pos); if(s.at(pos) == '1') n++; else n--; }; auto dfs3 = [&](auto dfs3,int pos,int back) -> void { if(s.at(pos) == '1') n++; else n--; Z.update(n,1); for(auto to : Graph.at(pos)) if(to != back) dfs3(dfs3,to,pos); if(s.at(pos) == '1') n--; else n++; }; for(auto to : Graph.at(pos)){ if(to == back || to == big) continue; dfs2(dfs2,to,pos); if(s.at(pos) == '1') n++; else n--; dfs3(dfs3,to,pos); if(s.at(pos) == '1') n--; else n++; } return n; } }; dfs(dfs,0,-1); cout << answer << endl; }