結果
| 問題 | No.2892 Lime and Karin |
| ユーザー |
 GOTKAKO
|
| 提出日時 | 2024-09-14 00:56:24 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 207 ms / 8,000 ms |
| コード長 | 6,270 bytes |
| コンパイル時間 | 2,601 ms |
| コンパイル使用メモリ | 209,832 KB |
| 最終ジャッジ日時 | 2025-02-24 08:23:00 |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 52 |
ソースコード
#include <bits/stdc++.h>using namespace std;using SS = int;class SegmentTree{public:int siz = 1,n;vector<SS> 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<SS> &A){make(N);for(int i=0; i<N; i++){int pos = i+siz;dat.at(pos) = A.at(i);}for(int i=siz-1; i>0; 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<bool(SS)> f,int l = 0){l += siz; int r = n+siz;vector<int> 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<ls.size(); i++){l = ls.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;}for(int i=rs.size()-1; 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<bool(SS)> f,int r = -1){if(r == -1) r = n;int l = siz; r += siz;vector<int> 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<rs.size(); i++){r = rs.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;}}for(int i=ls.size()-1; 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<vector<int>> Graph(N);for(int i=0; i<N-1; i++){int u,v; cin >> u >> v;u--; v--;Graph.at(u).push_back(v);Graph.at(v).push_back(u);}vector<int> 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;}