結果

問題 No.2892 Lime and Karin
ユーザー 👑 seekworserseekworser
提出日時 2024-07-05 13:47:00
言語 C++23
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,599 ms / 8,000 ms
コード長 3,703 bytes
コンパイル時間 5,625 ms
コンパイル使用メモリ 293,240 KB
実行使用メモリ 33,572 KB
最終ジャッジ日時 2024-07-05 21:11:17
合計ジャッジ時間 41,170 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,248 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 3 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 3 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 453 ms
11,596 KB
testcase_15 AC 472 ms
11,264 KB
testcase_16 AC 797 ms
15,320 KB
testcase_17 AC 166 ms
6,540 KB
testcase_18 AC 807 ms
15,236 KB
testcase_19 AC 1,113 ms
19,956 KB
testcase_20 AC 49 ms
5,376 KB
testcase_21 AC 555 ms
12,704 KB
testcase_22 AC 794 ms
15,112 KB
testcase_23 AC 289 ms
8,452 KB
testcase_24 AC 1,137 ms
20,176 KB
testcase_25 AC 1,097 ms
20,176 KB
testcase_26 AC 1,101 ms
20,184 KB
testcase_27 AC 1,096 ms
20,196 KB
testcase_28 AC 1,086 ms
20,184 KB
testcase_29 AC 1,090 ms
20,368 KB
testcase_30 AC 1,141 ms
20,140 KB
testcase_31 AC 1,086 ms
20,172 KB
testcase_32 AC 1,120 ms
20,304 KB
testcase_33 AC 1,098 ms
20,188 KB
testcase_34 AC 256 ms
26,580 KB
testcase_35 AC 259 ms
26,512 KB
testcase_36 AC 263 ms
26,636 KB
testcase_37 AC 267 ms
26,512 KB
testcase_38 AC 275 ms
26,504 KB
testcase_39 AC 2,599 ms
32,992 KB
testcase_40 AC 1,810 ms
33,572 KB
testcase_41 AC 1,218 ms
27,748 KB
testcase_42 AC 1,243 ms
33,464 KB
testcase_43 AC 1,225 ms
29,624 KB
testcase_44 AC 381 ms
9,608 KB
testcase_45 AC 1,018 ms
18,464 KB
testcase_46 AC 476 ms
11,036 KB
testcase_47 AC 593 ms
13,256 KB
testcase_48 AC 233 ms
7,832 KB
testcase_49 AC 770 ms
14,676 KB
testcase_50 AC 688 ms
23,448 KB
testcase_51 AC 695 ms
23,224 KB
testcase_52 AC 642 ms
23,336 KB
testcase_53 AC 674 ms
23,336 KB
testcase_54 AC 749 ms
23,392 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/convolution.hpp>
using namespace std;
using ll = long long;

vector<ll> multiply(vector<ll> a, vector<ll> b) { return atcoder::convolution_ll(a, b); }

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 = atcoder::convolution_ll(total, total);
        gmax *= 2;
        for (size_t i=0; i<f.size(); i++) {
            f[i] = atcoder::convolution_ll(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