結果

問題 No.2892 Lime and Karin
ユーザー hongrockhongrock
提出日時 2024-09-13 23:16:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 177 ms / 8,000 ms
コード長 2,130 bytes
コンパイル時間 2,224 ms
コンパイル使用メモリ 204,784 KB
実行使用メモリ 50,184 KB
最終ジャッジ日時 2024-09-13 23:16:26
合計ジャッジ時間 8,669 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge6
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 5 ms
8,192 KB
testcase_01 AC 5 ms
8,192 KB
testcase_02 AC 5 ms
8,192 KB
testcase_03 AC 5 ms
8,064 KB
testcase_04 AC 5 ms
8,064 KB
testcase_05 AC 6 ms
8,064 KB
testcase_06 AC 5 ms
8,192 KB
testcase_07 AC 5 ms
8,064 KB
testcase_08 AC 5 ms
8,064 KB
testcase_09 AC 5 ms
8,192 KB
testcase_10 AC 6 ms
8,064 KB
testcase_11 AC 5 ms
8,192 KB
testcase_12 AC 6 ms
8,064 KB
testcase_13 AC 5 ms
8,192 KB
testcase_14 AC 76 ms
12,544 KB
testcase_15 AC 65 ms
12,416 KB
testcase_16 AC 126 ms
14,864 KB
testcase_17 AC 27 ms
10,112 KB
testcase_18 AC 114 ms
14,848 KB
testcase_19 AC 165 ms
17,000 KB
testcase_20 AC 13 ms
8,832 KB
testcase_21 AC 88 ms
13,184 KB
testcase_22 AC 106 ms
14,592 KB
testcase_23 AC 46 ms
11,136 KB
testcase_24 AC 170 ms
16,968 KB
testcase_25 AC 174 ms
17,152 KB
testcase_26 AC 169 ms
17,076 KB
testcase_27 AC 162 ms
17,256 KB
testcase_28 AC 177 ms
17,292 KB
testcase_29 AC 169 ms
17,172 KB
testcase_30 AC 167 ms
17,152 KB
testcase_31 AC 166 ms
17,144 KB
testcase_32 AC 172 ms
17,144 KB
testcase_33 AC 169 ms
17,216 KB
testcase_34 AC 61 ms
15,676 KB
testcase_35 AC 62 ms
15,680 KB
testcase_36 AC 64 ms
15,676 KB
testcase_37 AC 68 ms
15,804 KB
testcase_38 AC 65 ms
15,804 KB
testcase_39 AC 145 ms
34,872 KB
testcase_40 AC 147 ms
47,816 KB
testcase_41 AC 132 ms
36,480 KB
testcase_42 AC 155 ms
50,184 KB
testcase_43 AC 139 ms
40,764 KB
testcase_44 AC 57 ms
11,776 KB
testcase_45 AC 138 ms
15,972 KB
testcase_46 AC 62 ms
12,276 KB
testcase_47 AC 89 ms
13,440 KB
testcase_48 AC 39 ms
10,496 KB
testcase_49 AC 111 ms
14,464 KB
testcase_50 AC 105 ms
16,832 KB
testcase_51 AC 120 ms
16,800 KB
testcase_52 AC 116 ms
16,768 KB
testcase_53 AC 112 ms
16,820 KB
testcase_54 AC 116 ms
16,768 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;

#define pb emplace_back
#define mp make_pair
 
using ll = long long;
using pii = pair<int,int>;
 
constexpr int mod = 998244353;
constexpr int inf = 0x3f3f3f3f;
constexpr int N = 1e5 + 10;
constexpr int M = 4e6 + 10;

int n, val[N], tree[N], node_cnt, lch[M], rch[M], sum[M], buf_len, buf[M];
char s[N];
vector<int> G[N];
vector<int> V[N];
ll ans;

int newnode(){
  int o;
  if(buf_len){
    o = buf[--buf_len];
  } else {
    o = ++node_cnt;
  }
  lch[o] = rch[o] = 0;
  sum[o] = 0;
  return o;
}

void add(int &o, int L, int R, int p, int v){
  if(!o)  o = newnode();
  sum[o] += v;
  if(L == R){
    return;
  }
  int mid = (L + R) >> 1;
  if(p <= mid)  add(lch[o], L, mid, p, v);
  else  add(rch[o], mid + 1, R, p, v);
}

int query(int o, int L, int R, int l, int r){
  if(!o)  return 0;
  if(L == l && R == r)  return sum[o];
  int mid = (L + R) >> 1;
  if(r <= mid)  return query(lch[o], L, mid, l, r);
  if(l > mid) return query(rch[o], mid + 1, R, l, r);
  return query(lch[o], L, mid, l, mid) + query(rch[o], mid + 1, R, mid + 1, r);
}

void walk(int o){
  if(!o)  return;
  walk(lch[o]);
  walk(rch[o]);
  buf[buf_len++] = o;
}

void join(int x, int y, int fa){
  if(G[x].size() < G[y].size()){
    swap(G[x], G[y]);
    swap(tree[x], tree[y]);
  }
  for(int v : G[y]){
    int target = val[x] + val[fa] - v + 1;
    if(target <= N){
      ans += query(tree[x], -N, N, max(target, -N), N);
    }
    G[x].pb(v);
  }
  for(int v : G[y]){
    add(tree[x], -N, N, v, 1);
  }
  G[y].clear();
  walk(tree[y]);
}

void dfs(int x, int fa){
  if(s[x-1] == '1'){
    val[x] = 1;
    ++ans;
  } else {
    val[x] = -1;
  }
  val[x] += val[fa];
  tree[x] = newnode();
  add(tree[x], -N, N, val[x], 1);
  G[x].pb(val[x]);
  for(int y : V[x]){
    if(y == fa) continue;
    dfs(y, x);
    join(x, y, fa);
  }
}

void _main(){
  int x, y;
  cin >> n;
  for(int i=1; i<n; ++i){
    cin >> x >> y;
    V[x].pb(y);
    V[y].pb(x);
  }
  cin >> s;
  val[0] = 0;
  dfs(1, 0);
  cout << ans << '\n';
}

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  _main();
  return 0;
}
0