結果

問題 No.2892 Lime and Karin
ユーザー FUN_MorikuboFUN_Morikubo
提出日時 2024-09-13 23:18:39
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 225 ms / 8,000 ms
コード長 3,418 bytes
コンパイル時間 8,060 ms
コンパイル使用メモリ 336,608 KB
実行使用メモリ 28,060 KB
最終ジャッジ日時 2024-09-13 23:18:55
合計ジャッジ時間 15,381 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,812 KB
testcase_02 AC 2 ms
6,944 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 91 ms
15,188 KB
testcase_15 AC 85 ms
14,352 KB
testcase_16 AC 147 ms
21,688 KB
testcase_17 AC 33 ms
8,404 KB
testcase_18 AC 145 ms
22,764 KB
testcase_19 AC 213 ms
27,556 KB
testcase_20 AC 11 ms
6,940 KB
testcase_21 AC 111 ms
16,224 KB
testcase_22 AC 140 ms
22,468 KB
testcase_23 AC 55 ms
10,276 KB
testcase_24 AC 214 ms
27,524 KB
testcase_25 AC 221 ms
26,392 KB
testcase_26 AC 218 ms
26,444 KB
testcase_27 AC 221 ms
27,800 KB
testcase_28 AC 225 ms
27,504 KB
testcase_29 AC 215 ms
27,460 KB
testcase_30 AC 217 ms
27,828 KB
testcase_31 AC 219 ms
27,540 KB
testcase_32 AC 224 ms
27,504 KB
testcase_33 AC 223 ms
27,600 KB
testcase_34 AC 115 ms
24,352 KB
testcase_35 AC 118 ms
24,384 KB
testcase_36 AC 116 ms
24,432 KB
testcase_37 AC 116 ms
24,536 KB
testcase_38 AC 116 ms
24,360 KB
testcase_39 AC 159 ms
26,416 KB
testcase_40 AC 157 ms
26,348 KB
testcase_41 AC 156 ms
26,284 KB
testcase_42 AC 142 ms
25,980 KB
testcase_43 AC 152 ms
28,060 KB
testcase_44 AC 73 ms
13,028 KB
testcase_45 AC 187 ms
26,024 KB
testcase_46 AC 84 ms
14,820 KB
testcase_47 AC 118 ms
16,268 KB
testcase_48 AC 47 ms
9,468 KB
testcase_49 AC 140 ms
22,084 KB
testcase_50 AC 169 ms
25,988 KB
testcase_51 AC 167 ms
25,948 KB
testcase_52 AC 165 ms
25,896 KB
testcase_53 AC 161 ms
25,500 KB
testcase_54 AC 168 ms
26,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using ll = long long;
template <class T> using vec = vector<T>;
template <class T> using vv = vec<vec<T>>;
template <class T> using vvv = vec<vv<T>>;
using vl = vec<ll>;
using vvl = vv<ll>;
#define rep(i, n) for (ll i = 0; i < ll(n); i++)
#define eb emplace_back

#include <atcoder/all>
using namespace atcoder;

ll op(ll a, ll b) { return a + b; }
ll e() { return 0; }
void solve() {
  ll n;
  cin >> n;
  vvl g(n);
  rep(i, n - 1) {
    ll u, v;
    cin >> u >> v;
    u--, v--;
    g[u].eb(v);
    g[v].eb(u);
  }
  string s;
  cin >> s;

  vl bfs;
  bfs.reserve(n);
  vl par(n, -1), sz(n, 1), depth(n, 0);
  vvl child(n);
  {
    queue<ll> q({0});
    while (q.size() > 0) {
      ll now = q.front();
      q.pop();
      bfs.eb(now);
      for (auto to : g[now]) {
        if (par[now] == to) continue;
        par[to] = now;
        q.push(to);
      }
    }
  }
  for (auto now : bfs | views::reverse) {
    for (auto to : g[now]) {
      if (par[now] == to) continue;
      sz[now] += sz[to];
      depth[now] = max(depth[now], depth[to] + 1);
      child[now].eb(to);
      if (sz[child[now][0]] < sz[child[now].back()])
        swap(child[now][0], child[now].back());
    }
  }

  // rep(now, n) cout << sz[now] << " ";
  // cout << "\n";

  using SEG = segtree<ll, op, e>;
  ll ans = 0;
  auto dfs = [&](auto f, ll now) -> tuple<ll, SEG, ll> {
    ll cur = now;
    ll seg_sz = 2 * sz[now] + 3;
    SEG seg(seg_sz);
    ll diff = sz[now] + 1;
    while (child[cur].size() > 0) cur = child[cur][0];

    while (true) {
      seg.set(diff, seg.get(diff) + 1);
      if (s[cur] == '0')
        diff--;
      else
        diff++;
      // if (seg.prod(0, diff) > 0)
      //   cout << cur << ", + " << seg.prod(0, diff) << "\n";
      ans += seg.prod(0, diff);

      for (ll i = 1; i < child[cur].size(); i++) {
        ll to = child[cur][i];
        auto [c_diff, c_seg, c_seg_sz] = f(f, to);
        for (ll j = 0; j < c_seg_sz; j++) {
          ll c_idx = j - c_diff;
          ll idx = diff - c_idx;
          if (idx < 0 || seg_sz < idx) continue;
          ll tmp = seg.prod(0, idx) * c_seg.get(j);
          ans += tmp;
          // if (tmp > 0) cout << cur << ", " << to << ", + " << tmp << "\n";
        }
        for (ll j = 0; j < c_seg_sz; j++) {
          ll c_idx = j - c_diff;
          ll idx = c_idx + diff;
          if (s[cur] == '0') idx++;
          else idx--;
          if (idx < 0 || seg_sz <= idx) continue;
          ll tmp = c_seg.get(j);
          if (tmp == 0) continue;
          tmp += seg.get(idx);
          seg.set(idx, tmp);
        }
        // cout << "cur, diff: " << cur << " " << diff << "\n";
        // rep(i, diff) cout << seg.get(i) << " |"[i + 1 == diff];
        // cout << seg.get(diff) << "|";
        // for (ll i = diff + 1; i < seg_sz; i++) cout << seg.get(i) << " ";
        // cout << "\n";
      }
      // if (child[cur].size() <= 1) {
      //   cout << "cur, diff: " << cur << " " << diff << "\n";
      //   rep(i, diff) cout << seg.get(i) << " |"[i + 1 == diff];
      //   cout << seg.get(diff) << "|";
      //   for (ll i = diff + 1; i < seg_sz; i++) cout << seg.get(i) << " ";
      //   cout << "\n";
      // }
      if (cur == now) return {diff, seg, seg_sz};
      cur = par[cur];
    }
  };
  dfs(dfs, 0);
  cout << ans << "\n";
}

int main() {
  ll t = 1;
  // cin >> t;
  rep(i, t) solve();
}
0