結果

問題 No.2892 Lime and Karin
ユーザー FUN_MorikuboFUN_Morikubo
提出日時 2024-09-13 23:16:24
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 3,315 bytes
コンパイル時間 7,985 ms
コンパイル使用メモリ 337,172 KB
実行使用メモリ 28,172 KB
最終ジャッジ日時 2024-09-13 23:16:52
合計ジャッジ時間 20,491 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 2 ms
6,812 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,940 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,944 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 AC 104 ms
24,524 KB
testcase_35 AC 104 ms
24,468 KB
testcase_36 AC 106 ms
24,316 KB
testcase_37 AC 110 ms
24,248 KB
testcase_38 AC 104 ms
24,388 KB
testcase_39 RE -
testcase_40 RE -
testcase_41 AC 153 ms
26,420 KB
testcase_42 AC 148 ms
25,960 KB
testcase_43 AC 149 ms
28,172 KB
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
testcase_54 RE -
権限があれば一括ダウンロードができます

ソースコード

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] + 1;
    SEG seg(seg_sz);
    ll diff = sz[now];
    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;
          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--;
          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