結果

問題 No.2892 Lime and Karin
ユーザー 👑 seekworserseekworser
提出日時 2024-07-13 18:31:02
言語 C++23(gcc13)
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 4,090 bytes
コンパイル時間 7,214 ms
コンパイル使用メモリ 333,008 KB
実行使用メモリ 32,012 KB
最終ジャッジ日時 2024-07-13 18:31:35
合計ジャッジ時間 26,244 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 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,940 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 1 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,944 KB
testcase_10 AC 2 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 216 ms
10,368 KB
testcase_15 AC 209 ms
10,004 KB
testcase_16 AC 391 ms
14,336 KB
testcase_17 AC 82 ms
6,944 KB
testcase_18 AC 370 ms
14,372 KB
testcase_19 AC 504 ms
17,392 KB
testcase_20 AC 38 ms
6,944 KB
testcase_21 AC 255 ms
11,384 KB
testcase_22 AC 345 ms
14,200 KB
testcase_23 AC 132 ms
8,056 KB
testcase_24 AC 557 ms
17,884 KB
testcase_25 AC 518 ms
17,736 KB
testcase_26 AC 508 ms
17,740 KB
testcase_27 AC 543 ms
17,756 KB
testcase_28 AC 523 ms
17,620 KB
testcase_29 AC 550 ms
17,664 KB
testcase_30 AC 543 ms
17,620 KB
testcase_31 AC 564 ms
17,732 KB
testcase_32 AC 518 ms
17,600 KB
testcase_33 AC 546 ms
17,744 KB
testcase_34 AC 158 ms
25,676 KB
testcase_35 WA -
testcase_36 WA -
testcase_37 WA -
testcase_38 WA -
testcase_39 AC 862 ms
29,080 KB
testcase_40 AC 665 ms
32,012 KB
testcase_41 AC 519 ms
25,168 KB
testcase_42 AC 529 ms
31,012 KB
testcase_43 AC 561 ms
26,980 KB
testcase_44 AC 182 ms
9,088 KB
testcase_45 AC 462 ms
16,332 KB
testcase_46 AC 247 ms
9,840 KB
testcase_47 AC 271 ms
11,900 KB
testcase_48 AC 114 ms
7,656 KB
testcase_49 AC 335 ms
13,588 KB
testcase_50 AC 342 ms
21,656 KB
testcase_51 WA -
testcase_52 AC 338 ms
21,540 KB
testcase_53 WA -
testcase_54 AC 363 ms
21,628 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

//line 1 "answer.cpp"
#include <bits/stdc++.h>

#include <atcoder/convolution.hpp>
#include <atcoder/modint.hpp>
using namespace std;
using ll = long long;
using mint = atcoder::modint998244353;

vector<ll> multiply(vector<ll> a, vector<ll> b) {
    vector<mint> a_mod(a.begin(), a.end());
    vector<mint> b_mod(a.begin(), a.end());
    auto result_mod = atcoder::convolution(a, b);
    vector<ll> result(result_mod.begin(), result_mod.end());
    return result;
}

int main() {
    ll n;
    cin >> n;
    vector g(n, vector<ll>(0));
    for (size_t i = 0; i < n - 1; i++) {
        ll u, v;
        cin >> u >> v;
        --u;
        --v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    string si;
    cin >> si;
    vector<ll> s(n);
    for (size_t i = 0; i < n; i++) s[i] = (si[i] == '0' ? -1 : 1);

    ll ans = 0;

    vector<bool> removed(n, false);
    vector<ll> sz(n, 0);
    auto centroid_decomposition = [&](auto self, ll x) -> void {
        auto calc_total_size = [&](auto self, ll u, ll par) -> ll {
            ll result = 1;
            for (auto v : g[u])
                if (v != par && !removed[v]) result += self(self, v, u);
            return result;
        };
        ll total_size = calc_total_size(calc_total_size, x, -1);
        ll m = (total_size + 1) / 2;
        auto find_centroid = [&](auto self, ll u, ll par) -> pair<ll, ll> {
            ll c = -1;
            ll mn = n + 1;
            sz[u] = 1;
            for (auto v : g[u]) {
                if (v == par || removed[v]) continue;
                auto [cn, mnn] = self(self, v, u);
                if (mnn < mn) {
                    mn = mnn;
                    c = cn;
                }
                sz[u] += sz[v];
            }
            if (sz[u] >= m && sz[u] < mn) {
                mn = sz[u];
                c = u;
            }
            return {c, mn};
        };
        auto [c, _] = find_centroid(find_centroid, x, -1);

        vector<vector<ll>> f(0);
        vector<ll> getas;

        for (auto v : g[c]) {
            if (removed[v]) continue;
            ll mx = 0;
            auto calc_geta = [&](auto self, ll u, ll par, ll x) -> ll {
                ll result = x;
                mx = max(mx, x);
                for (auto v : g[u]) {
                    if (v == par || removed[v]) continue;
                    result = min(result, self(self, v, u, x + s[v]));
                }
                return result;
            };
            ll geta = max(0LL, -calc_geta(calc_geta, v, c, s[v]));
            f.push_back(vector<ll>(mx + geta + 1, 0));
            getas.push_back(geta);
            auto calc_f = [&](auto self, ll u, ll par, ll x) -> void {
                f[f.size() - 1][x + geta] += 1;
                for (auto v : g[u]) {
                    if (v == par || removed[v]) continue;
                    self(self, v, u, x + s[v]);
                }
            };
            calc_f(calc_f, v, c, s[v]);
        }

        ll gmax = 0;
        for (auto gi : getas) gmax = max(gmax, gi);
        vector<ll> total(gmax + sz[x], 0);
        for (size_t i = 0; i < f.size(); i++) {
            for (size_t j = 0; j < f[i].size(); j++) {
                total[j - getas[i] + gmax] += f[i][j];
            }
        }
        for (size_t i = gmax + 1 - s[c]; i < total.size(); i++) ans += total[i];

        total = multiply(total, total);
        gmax *= 2;
        for (size_t i = 0; i < f.size(); i++) {
            f[i] = multiply(f[i], f[i]);
            getas[i] *= 2;
            for (size_t j = 0; j < f[i].size(); j++) {
                if (f[i][j] != 0) total[j - getas[i] + gmax] -= f[i][j];
            }
        }
        for (size_t i = gmax + 1 - s[c]; i < total.size(); i++)
            ans += total[i] / 2;

        removed[c] = true;
        for (auto v : g[c]) {
            if (!removed[v]) self(self, v);
        }
        return;
    };
    centroid_decomposition(centroid_decomposition, 0);
    ll add = 0;
    for (size_t i = 0; i < n; i++) add += (si[i] - '0');
    cout << ans + add << endl;
    return 0;
}
0