AOJ 0389 Dungeon 2

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0389

解法

木DP。つらい。
以下自分の解き方を書くけど、他の人のコード読む限り状態数はまだ減らせそう？
すくなくともテーブルでもつ必要のある状態は減らせると思う。まあいいか。

まず、部分木の根が全体としてどういう使われ方をしうるかを丁寧に見よう。
適当に考えると少なくとも以下の4通り考えればよさそう。

• 場合1：根ノードが始点。終点は（部分木の）どこでも
• 場合2：根ノードが終点。始点は（部分木の）どこでも
• 場合3：根ノードが始点かつ終点
• 場合4：根ノードはウォークの中間頂点

場合1：根ノードが始点

子から場合3のもので得をするものを使う。
また、子のうち一つは場合1のものを選択して良い。

場合2：根ノードが終点

子から場合3のもので得をするものを使う。
また、子のうち1つは場合2のものを使って良い。
ほとんど場合1と同じ。

場合3

子から場合3のもので得をするものを使う。以上

場合4

これはちょっと面倒だった。大きく分けて2通りあるからである。

• 場合3の子ノードで得をするものを使う。子のうち1つは場合4のものを選択
• 場合3の子ノードで特をするものを使う。子のうち2つは場合2と場合1を1つずつ選択

1つ目については、例えば子 v が中間頂点とするウォークを考えると、v から今の頂点に寄り道してまた子 v に戻るようなウォークがあるからである。
2つ目は、子 c1 から今の頂点に移ってきて、また別の子 c2 に入っていくようなウォークである。
2つ目はいいけど1つ目のを忘れやすい気がする。状態の持ち方によるかも。

計算量は O(nlogn)

ソースコード

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

using pii = pair<int, int>;

constexpr int inf = 1e9;

int main() {
    int n; cin >> n;
    vector<int> p(n);
    vector<vector<int>> g(n);
    for(int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    for(int i = 0; i < n - 1; ++i) {
        int s, t; cin >> s >> t;
        g[s - 1].push_back(t - 1);
        g[t - 1].push_back(s - 1);
    }

    // 0: start, 1: last, 2: start & last, 3: inter
    int ans = -inf;
    vector<vector<int>> dp(n, vector<int>(4, -inf));
    function<void(int, int)> dfs = [&] (int v, int par) {
        dp[v][0] = dp[v][1] = dp[v][2] = dp[v][3] = p[v];
        vector<int> ch0, ch1, ch2;
        vector<pii> sub0, sub1;
        int sum2 = 0, max_sub3 = 0;
        for(auto to : g[v]) {
            if(to == par) continue;
            dfs(to, v);
            ch0.push_back(max(0, dp[to][0] - 1));
            ch1.push_back(max(0, dp[to][1] - 1));
            ch2.push_back(max(0, dp[to][2] - 2));
            sub0.emplace_back(ch0.back() - ch2.back(), to);
            sub1.emplace_back(ch1.back() - ch2.back(), to);
            max_sub3 = max(max_sub3, max(0, dp[to][3] - 2) - ch2.back());
            sum2 += ch2.back();
        }
        const int sz = ch0.size();
        sort(rbegin(sub0), rend(sub0));
        sort(rbegin(sub1), rend(sub1));
        for(int i = 0; i < sz; ++i) {
            dp[v][0] = max(dp[v][0], sum2 + ch0[i] - ch2[i] + p[v]);
            dp[v][1] = max(dp[v][0], sum2 + ch1[i] - ch2[i] + p[v]);
        }
        dp[v][2] = max(dp[v][2], sum2 + p[v]);
        // inter
        dp[v][3] = max(dp[v][3], sum2 + max_sub3 + p[v]);
        if(sz >= 2) {
            for(int i = 0; i < 2; ++i) {
                for(int j = 0; j < 2; ++j) {
                    if(i == j || sub0[i].second == sub1[j].second) continue;
                    dp[v][3] = max(dp[v][3], sum2 + sub0[i].first + sub1[j].first + p[v]);
                }
            }
        }
        ans = max(ans, *max_element(begin(dp[v]), end(dp[v])));
    };
    dfs(0, -1);

    cout << ans << endl;
}

感想

木DP、毎回頭壊れるんだけどどうすればええんや…
なんか遷移が難しいのばっかりなんだよね。実装が悪いのかなあ。

ACM-ICPC 2018 Seoul Regional 参加記 （コンテスト以外）

はじめに

2018年に韓国で行われた ICPC Seoul Regional の参加記です。
自分はチーム Zerokan_Sunshine としてでました。
チームメイトはいつもの kazuma, nakano です。

この記事はコンテスト以外の部分に絞って書いたものです。
コンテストの内容はこちらから。
suikaba.hatenablog.com

箇条書き形式で書きます。

各日の流れ

出発前日 (10/31)

• 生活習慣が壊れていたので当然のように徹夜することになる。

出発日 (11/1)

• 12時ぐらいに出発するいいチケットが取れた
• 韓国近い、一瞬で到着する
• 仁川国際空港で昼ごはん。そんなに辛くない

• ホテルまでが遠すぎる（空港から2時間ぐらい）
• 晩ごはん

• 晩御飯の店、完全に韓国語 only で何言ってるか全くわからなかった
  • 自分が何を注文したのかもわからないまま大量のご飯が出てきた
  • ちなみにかなり美味しかった
• 疲れたので適当に就寝

プラクティス (11/2)

• 朝はロッテリア
• 大学までは近かったので歩いていった
• プラクティスはまあ適当に、A問題は不可能だった
• 晩ごはん（会津勢と食べたかったけど、ホテルも遠いしいろいろあってご一緒できなかった）
  • 写真の左のやつがかなり辛かった
  • これとは別に唐辛子単体で出てきたからまるごと一気に食べた
  • これが完全にミスで、あまりの辛さに10分ぐらい喋れなくなった
  • 翌日ずっとお腹壊れてたの完全にこれのせいだろ

本番 (11/3)

• 朝は SUBWAY
• コンテストは別の記事に
• 閉会式がほぼほぼ韓国語 only だったので、はっきり言ってかなり暇だった
• yes/no おじさんが yes/no じゃなかった（韓国語なので）
• 晩御飯は懇親会で。日本と違い基本的に飯はずっと補給されてそう。まあまあ美味しかった
• 疲れたので帰って寝る…と言いたかったが Snackdown があった
• 仮眠とってから kazuma と出た。5完で150位ぐらいだったかも、まあ6完すべきだったぽいけど通過なのでセーフ
• ほんとに就寝

帰国 (11/4)

• 寝坊する
• 時間がないので急いで空港へ
• 昼ごはん。おいしい

• おみやげを買うはずが時間がない、適当に入ってなんか勧められた（？）やつを買う
  • 韓国のりかったら5000円ぐらいした、こんなに高いとは知らなかった
• 搭乗予定時刻より10分ぐらい遅刻したけど大丈夫だった
• 帰国

まとめ

観光できなかったのは残念だったけど、ご飯については割と色々食べられたので満足。
ホテルもいいところだったし。
もし今度来ることがあったら、そのときはちゃんと観光したい。

ACM-ICPC 2018 Seoul Regional 参加記 (コンテスト)

はじめに

2018年に韓国で行われた ICPC Seoul Regional の参加記です。
自分はチーム Zerokan_Sunshine としてでました。
チームメイトはいつもの kazuma, nakano です。

この記事はコンテストについて書いたものです。

チームの役割分担は以下の通り

• nakano （考察担当、基本的に実装はしない）
• kazuma （考察、実装担当、理想は僕と交代交代で書く）
• suibaka （実装担当、めんどくさいやつとかやるだけとか構文解析とか幾何とか）

ちなみに kazuma 視点の参加記もあります。
ICPC Seoul Regional 2018 参加記 - kazuma8128’s blog

コンテスト

一応コンテストの流れに沿って（覚えてる範囲で）書く。

D 問題

• PCの設定とかやってたら D がやるだけだと教えられる
• なんだこの問題はたまげたなあ
• AC（15分）

虚無

• いつもならここで次のコーディングにすぐ入るはず…
• しかし今日は書く問題が降ってこない、完全に異常事態
• どうもパット見の難易度判定に失敗しまくったらしい
  • D の次 C とか考え始めてたからね、やばいね
• ここでなんと1時間以上溶けた。

F 問題

• やることがないのでやるだけの F を書き始める
• さっさと解くつもりだったがバグる
• 一番外側にカッコが付いていてはいけないのを完全に忘却していて時間を溶かしてしまう
  • (a + b) とかはだめだったけど OK 判定だった
• K、L のあとになったけど通す。これは大反省

K 問題

• 僕が別のやってる間に kazuma にやってもらった
• nakano から問題概要を聞いた時、脳内で R, G, B の3色があると思って悩んだ
• nakano が2色だと教えてくれた
• kazuma も僕と同じく3色だと思っていたらしく、2色なら 2-SAT やるだけやんけ！となり、書いて AC (103min)

L 問題

• F がなぜか通らない（前述の通り）ので、最悪になる前に L を考える
• 連続して働く必要のある時間がバラバラだと思っていて、しばらく不可能じゃんとなっていた
• よく読んだら w は全員固定だった、じゃあ貪欲だねとなる
• 書いたらなんか RE した。理由は n と m を間違えていた（このミスするの何度目？
• AC (136min)
• ちなみに書いてる途中に腹痛がピークを迎えたので、「トイレに行っていい？」と kazuma に聞いたら「ACしたらいいよ」と言われた。鬼か？（まあ当然っちゃ当然ですが

G 問題

• nakano がずっと式やら図形やらとにらめっこして式を生成していた
• 生成したのを kazuma になげて書いて AC (172min)
• 積分せずに楽できるか、みたいな問題だったらしい？しらんけど

A 問題

• 実は最初からたまに考えていて、簡単に解けるんじゃないの？と思っていた
• しかし完全に虚無っていたのであまり詰められず、後半まで放置されていた
• kazuma に投げてしばらくしたら starry sky tree で殴れるね、となりそれで書いてもらうことに
• なんか細かいミスをしていたらしくWAが生えるが、まあすぐ修正して AC (237min)

B 問題

• nakano から概要を聞く
• nakano から解法を聞く
• 書いて AC (238min)
• なんでこの問題がここまで放置されていたかと言うと、ここまでなんと誰も読んでいなかった（は？？？）
• あと普通に問題文が難しすぎるだろ

E 問題

• これも最初に考えてはいたんだけど、うーむとなっていた
• kazuma はなんと max の部分が sum だと思っていたらしい、そりゃ解けんわ（勘違いしているとは思わなかった
• 解けることはわかっていたが、これに着手したのが最後の20分とかだったので間に合わず…

J 問題

• nakano に概要を教えてもらう
• 適当にマージしていったらできるんじゃないの、みたいなふわふわ解法で書き始める
• 入力を取るのが難しかった（変数の並びが不自然だったような…
• 書いた、バグバグ
• バグいっぱい
• というか解法間違えてない？間違えてるね
• 終了

C 問題

• AOJに似たやつがあったけど、あれは並び替え不可能だった
• どうせいい感じの並びが存在するに決まっていて、という感じだった
• しかしCの考察にさける時間がほとんどなく、結局よくわからない嘘を書いてサンプルが合わない、みたいなことになっていた気がする

I, H 問題

• 見るからにヤバイので自然に回避していた、結果的には正しかった

結果

7完 17th でした。大学別では10位という残念な結果に。
UKUNICHIA に負けたのは普通に悔しい。

反省

• 序盤の動き方が最悪で、ここまでひどいとリカバリー不可能
• とはいってもこのセットでパット見で難易度推定するのは今の自分達には厳しかったのかなあ
  • 簡単なのは問題文が難しい、読みやすいのは大体そこそこ難しい、みたいな
• Standings もあんまり活用できなかった、解かれる問題が割とバラバラだったので
• こういうときは他の人じゃなくて自分たちを信じて、あれこれ行ったり来たりせず解けそうと思った問題にある程度張り付いたほうが良かったのかも？
• 問題読解が雑すぎた。問題を難しくして解けなくするのは最もやってはいけないこと。
• 今回は自分はほとんど問題を読まなかったので、多分それも良くない
• 問題を読むときは Input/Output まできちんと読むべき
• 問題概要を伝えるときは、聞き手が勝手に脳内補完をしないような伝え方をすべき
• 逆に問題概要を聞くときは、勝手に脳内補完しないほうがいい

まとめ＆感想

今回のセットで10完が当たり前な韓国勢の恐ろしさを感じました。
普通に事故る可能性高いと思うんですが、そうでもないんでしょうか……。
せめて E は通したかったなーという感じです。J は厳しかったかも。
今の実力的には8完で及第点だったのかなと思っています。しかしうまくいかないもんだなあ。
でもいい経験になったと思って、横浜大会ではいい成績を残せるようがんばります。

Codeforces Round #320 (Div.1) C. Weakness and Poorness

* 問題文
http://codeforces.com/contest/578/problem/C

解法

max 取ってるし、x についての weakness を f(x) とすると、下に凸な関数になりそう。
なので3分探索する。
x を決めたときの a[i] - x 列の区間和最大、最小は線形で解ける。
左から累積和を見ていって、それまでの最大値と最小値を持っておけばOK。
よって O(nlog|a|) で解ける。

関係ないけど、区間Add区間和最大セグ木が途中でほしいなーと思って考えて、無理じゃね？となった。（区間Addで壊れる）

ソースコード

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

constexpr double inf = 1e9;
constexpr double gratio = (std::sqrt(5)+1)/2.0;

template <typename F>
double golden_section_search(F f, double lb, double ub, int cnt) {
    double x1 = (ub-lb)/(gratio+1) + lb,
        x2 = (ub-lb)*gratio/(gratio+1) + lb;
    double v1 = f(x1), v2 = f(x2);
    for(int i=0; i<cnt; ++i) {
        if(v1 < v2) {
            ub = x2;
            x2 = x1;
            v2 = v1;
            x1 = (ub-lb)/(gratio+1) + lb;
            v1 = f(x1);
        } else {
            lb = x1;
            x1 = x2;
            v1 = v2;
            x2 = (ub-lb)*gratio/(gratio+1) + lb;
            v2 = f(x2);
        }
    }
    return (lb+ub)/2;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cout << fixed << setprecision(10);
    int n; cin >> n;
    vector<double> a(n);
    for(int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    auto f = [&] (double x) {
        vector<double> sum(n + 1);
        double min_s = 0, max_s = 0;
        double res = 0;
        for(int i = 0; i < n; ++i) {
            sum[i + 1] = sum[i] + a[i] - x;
            res = max({res, abs(sum[i + 1] - max_s), abs(sum[i + 1] - min_s)});
            min_s = min(min_s, sum[i + 1]);
            max_s = max(max_s, sum[i + 1]);
        }
        return res;
    };
    const auto opti = golden_section_search(f, -10000, 10000, 100);
    cout << f(opti) << endl;
}

Codeforces Round #319 (Div.1) B. Invariance of Tree

問題文

http://codeforces.com/contest/576/problem/B

解法

自分は直感で、どうせ p に周期3以上のサイクルがあると困るんじゃないの、みたいに考えた。
周期3以上のサイクル内部で辺を張るとループができて困るので、そういう意味では正しい。
また、2つのサイクル c1 = (a1, a2, ..., ak), c2 = (b1, b2, ..., bm) があって、それらのうちから1つのペアを選んで結んでいくと、当然 a1-b1, a2-b2, ... のようにどんどん組まれていくことになる。
なので、k と m の長さが互いに素だとループができて困るなあということもわかる。

そして最も重要なこととして、こうして結んでできた連結成分の構造というのは、あるサイクルに含まれる頂点ごとに注目すると全く同じである。
つまり、ある段階で a1, a2, ... が属する連結成分をそれぞれ見ると、全く同じグラフになっているということ。
これと、木の中心はたかだか2個しかないという性質から、以下のことがわかる。
「周期1または2のサイクルがない場合、構築不可能である」
周期3以上のサイクル内の頂点が中心になるとすると、他の頂点もすべて中心になっているはずなので、それは矛盾だからである。

・周期1のサイクルがある場合
その頂点を他の全部の頂点と結べばOK
・周期1のサイクルがなく、周期2のサイクルがある場合
周期が互いに素だと困るなあ、というのはここで使う。つまり、周期が奇数のサイクルがあれば構築不可能であり、そうでなければ交互に結んでいけばOK。
例えば (a1, a2) と (b1, b2, b3, b4) があれば (a1, b1), (a2, b2), (a1, b3), (a2, b4) と辺を作る。
このときにサイクルの順番は崩さないように。union_find でサイクルを求めてしまって、順番が壊れたまま構築するとWAになる（僕はやらかしました、詰めが甘いね）。

これで解ける。オーダーは O(N)

ソースコード

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

using pii = pair<int, int>;

int main() {
    int n; cin >> n;
    vector<int> p(n);
    for(int i = 0; i < n; ++i) {
        cin >> p[i];
        p[i]--;
    }

    vector<bool> visited(n);
    function<void(int, vector<int>& vs)> dfs = [&] (int v, vector<int>& vs) {
        if(visited[v]) return;
        visited[v] = true;
        vs.push_back(v);
        dfs(p[v], vs);
    };
    vector<vector<int>> cmp;
    int sz1_v = -1;
    int sz2_cmp = -1, odd = 0;
    for(int i = 0; i < n; ++i) {
        if(visited[i]) continue;
        vector<int> vs;
        dfs(i, vs);
        if(vs.size() == 1u) {
            sz1_v = i;
        }
        if(vs.size() == 2u) {
            sz2_cmp = cmp.size();
        }
        odd += vs.size() & 1;
        cmp.push_back(move(vs));
    }
    if(sz1_v != -1) {
        cout << "YES" << endl;
        for(int i = 0; i < n; ++i) {
            if(i == sz1_v) continue;
            cout << sz1_v + 1 << ' ' << i + 1 << endl;
        }
    } else if(sz2_cmp != -1 && odd == 0) {
        cout << "YES" << endl;
        cout << cmp[sz2_cmp][0] + 1 << ' ' << cmp[sz2_cmp][1] + 1 << endl;
        for(int i = 0; i < (int)cmp.size(); ++i) {
            if(sz2_cmp == i) continue;
            for(int j = 0; j < (int)cmp[i].size(); j += 2) {
                cout << cmp[sz2_cmp][0] + 1 << ' ' << cmp[i][j] + 1 << endl;
                cout << cmp[sz2_cmp][1] + 1 << ' ' << cmp[i][j + 1] + 1 << endl;
            }
        }
    } else {
        cout << "NO" << endl;
    }
}

感想

時間内に解けなかった。
解説に "It's easy to notice, that centers of that tree must turn into centers after applying the permutation. That means, permutation must have cycle with length 1 or 2 since there're at most two centers" と書いてあって、最初な～にが easy じゃとなっていた。
union find 使って失敗したのも反省（当たり前なのにね、意外と気づかなかった）。

Bubble Cup 8 - Finals G. Run for beer

問題文

http://codeforces.com/contest/575/problem/G

解法

1ステップごとにコストが10倍になり、かつ辺のコストは高々9であることから、通った道を前から見て10進表記したものがコストなので、できるだけ短いほうがいいことにはすぐ気がつく。

同じ長さならコストが小さいほうがいいが、コストを保持してダイクストラは不可能なので面倒。
とりあえず、今の（これまでに移動した回数、直前の辺のコスト）で最短経路問題を解き、最短路グラフもどきを作る。直前の辺のコストしか見ていないから、真の最短路ではない辺も含まれている。

あとは最短路グラフ（もどき）の上でゴールから1ステップずつみていって、その時々で一番小さいコストの辺を使う頂点以外を取り除いていき、頂点0までたどり着けた頂点が真の最短路になる。

もう一つ面倒なのが、コスト0の辺があることで、こいつのせいで leading zero をいい感じに処理しないといけなくなる。というのも、0がたくさん頭につくときに、これまでに移動した回数をカウントしてしまうと、実際は0なのに最短路グラフ（もどき）に含まれなくなるからである。かといって0のときにカウントしない、みたいなこともできない。

なので、あらかじめ頂点 n - 1 からコスト0だけを使って辿れるところを BFS で列挙しておく（BFSじゃないとパスの長さの最小化にならないので注意）。ここでも最短路グラフを作っておく。

さっきの始点から始める最短経路計算のゴールを、頂点 n - 1 じゃなくて、このBFSで辿れた頂点のうちのどこでもよい、とする。

最後に、その頂点まで至る最短路と、その頂点から終点までに至る最短路を別に復元すればOK。

計算量は O(mlogn + n) 。ダイクストラしてるからね。

ソースコード

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

using ll = long long;
using pii = pair<int, int>;

constexpr int inf = 1e9;

struct edge {
    int to, cost;
};

using graph = vector<vector<edge>>;

int main() {
    int n, m; cin >> n >> m;
    graph g(n);
    for(int i = 0; i < m; ++i) {
        int a, b, c; cin >> a >> b >> c;
        g[a].push_back(edge{b, c});
        g[b].push_back(edge{a, c});
    }
    vector<int> to(n, -1), len(n, inf);
    {
        queue<int> que;
        que.push(n - 1);
        len[n - 1] = 0;
        while(!que.empty()) {
            const auto v = que.front(); que.pop();
            for(auto& e : g[v]) {
                if(e.cost != 0 || len[e.to] != inf) continue;
                to[e.to] = v;
                len[e.to] = len[v] + 1;
                que.push(e.to);
            }
        }
    }

    using S = tuple<int, int, int, int>;
    priority_queue<S, vector<S>, greater<>> que;
    que.emplace(0, 0, len[0], 0);
    vector<pii> d(n, make_pair(inf, inf));
    d[0] = make_pair(0, 0);
    vector<vector<pii>> prev(n);
    int last_v = -1;
    while(!que.empty()) {
        int dn, pre_d, zero_len, v;
        tie(dn, pre_d, zero_len, v) = que.top(); que.pop();
        if(d[v] < make_pair(dn, pre_d)) continue;
        if(to[v] != -1 || v == n - 1) { // answer
            last_v = v;
            break;
        }
        for(auto& e : g[v]) {
            if(d[e.to] > make_pair(dn + 1, e.cost)) {
                d[e.to] = make_pair(dn + 1, e.cost);
                prev[e.to].clear();
                prev[e.to].emplace_back(v, e.cost);
                que.emplace(dn + 1, e.cost, len[e.to], e.to);
            } else if(d[e.to] == make_pair(dn + 1, e.cost)) {
                prev[e.to].emplace_back(v, e.cost);
            }
        }
    }

    string ans;
    vector<int> cur = {last_v}, prev2(n, -1);
    while(!cur.empty()) {
        int mini = 10;
        vector<int> nxt;
        for(auto v : cur) {
            for(auto& p : prev[v]) {
                if(mini > p.second) {
                    mini = p.second;
                    nxt.clear();
                    nxt.push_back(p.first);
                    prev2[p.first] = v;
                } else if(mini == p.second) {
                    prev2[p.first] = v;
                    nxt.push_back(p.first);
                }
            }
        }
        if(mini != 10) {
            ans += mini + '0';
        }
        cur = move(nxt);
    }
    if(ans.empty()) ans = "0";
    vector<int> path;
    {
        int now = 0;
        while(now != -1) {
            path.push_back(now);
            now = prev2[now];
        }
        now = last_v;
        while(to[now] != -1) {
            path.push_back(to[now]);
            now = to[now];
        }
    }

    const int sz = path.size();
    cout << ans << endl;
    cout << sz << endl;
    for(int i = 0; i < sz; ++i) {
        cout << path[i] << " \n"[i + 1 == sz];
    }
}

感想

公式解説だと O(n + m) らしい。すごいね。
無限にバグって辛かった（めんどくさいことが多すぎる）。

Codeforces Round #322 (Div.2) F. Zublicanes and Mumocrates

問題文

http://codeforces.com/contest/581/problem/F

解法

（知っていれば）二乗の木DPっぽいな～となり、実際そうである。
ひとまず普通に木DPをする。
dp[v][cnt][c] := v の部分木だけ考えて、その中の葉を cnt だけ黒く塗り、v の色が c であるときの最小値
とする。
遷移は
dp[v][cnt][c] := min(dp[v][cnt][c], dp[v][cnt - ch_cnt][c] + dp[to][ch_cnt][ch_c] + (c != ch_c)) (forall ch)
みたいなことをする。ただし、v が葉でない場合は、ひとまず dp[v] の初期値を子から1つ選んで初期化しておく必要がある。
以降は最初に選んだ子は無視して遷移する。
遷移するときに、今処理してる子による結果が影響しないようにしておくこと。

さて、問題は計算量だが、cnt と ch_cnt によるループで各ノードで O(n^2) かかるので、全体として O(n^3) っぽいが、実際はそれほど計算が発生しない。

かなり大雑把に捉えるなら、例えば2つの子を持つ部分木を考えて、子のサイズを l, r としたとき、T(l + r) = T(l) + T(r) + l * r のような計算量の漸化式を考えると良い。
(l + r)^2 = l^2 + r^2 + l * r なので、T(n) = n^2 とみなせることがなんとなくわかるはず。

あとはMLEに注意する。あと、ループはきっちりサイズちょうどの上限で回さないと計算量が変わるので丁寧にやること。

ソースコード

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

constexpr int inf = 1e9;

int main() {
    int n; cin >> n;
    vector<vector<int>> g(n);
    for(int i = 0; i < n - 1; ++i) {
        int a, b; cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    if(n == 2) {
        cout << 1 << endl;
        return 0;
    }
    int root = -1;
    for(int i = 0; i < n; ++i) {
        if(g[i].size() != 1u) root = i;
    }

    vector<vector<vector<int>>> dp(n, vector<vector<int>>(2, vector<int>(2, inf)));
    vector<int> sz(n);
    function<void(int, int)> dfs = [&] (int v, int p) {
        if(g[v].size() == 1u) {
            sz[v] = 1;
            dp[v][0][0] = dp[v][1][1] = 0;
            return;
        }
        int fst_ch = -1;
        for(auto to : g[v]) {
            if(to == p) continue;
            if(fst_ch == -1) fst_ch = to;
            dfs(to, v);
        }
        {
            int sum = 0;
            for(auto to : g[v]) {
                if(to == p) continue;
                sum += sz[to];
            }
            dp[v].assign(sum + 1, vector<int>(2, inf));
        }
        for(auto to : g[v]) {
            if(to == p) continue;
            sz[v] += sz[to]; // !! add here
            if(to == fst_ch) {
                for(int cnt = 0; cnt <= sz[v]; ++cnt) {
                    for(int c = 0; c < 2; ++c) {
                        for(int cc = 0; cc < 2; ++cc) {
                            if(dp[to][cnt][cc] == inf) continue;
                            dp[v][cnt][c] = min(dp[v][cnt][c], dp[to][cnt][cc] + (c != cc));
                        }
                    }
                }
            } else {
                for(int cnt = sz[v]; cnt >= 0; --cnt) {
                    for(int c = 0; c < 2; ++c) {
                        int mini = inf;
                        for(int ch_cnt = 0; ch_cnt <= min(sz[to], cnt); ++ch_cnt) {
                            for(int ch_c = 0; ch_c < 2; ++ch_c) {
                                mini = min(mini, dp[v][cnt - ch_cnt][c] + dp[to][ch_cnt][ch_c] + (c != ch_c));
                            }
                        }
                        dp[v][cnt][c] = mini;
                    }
                }
            }
        }
    };
    dfs(root, -1);

    cout << min(dp[root][sz[root] / 2][0], dp[root][sz[root] / 2][1]) << endl;
}

感想

二乗の木DP、集中してコーディングしないとすぐバグるからつらい。