結果
| 問題 | 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;
}