結果

問題 No.763 Noelちゃんと木遊び
コンテスト
ユーザー sykwer
提出日時 2019-05-11 05:01:02
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 947 bytes
コンパイル時間 652 ms
コンパイル使用メモリ 69,504 KB
実行使用メモリ 816,528 KB
最終ジャッジ日時 2024-07-02 01:08:08
合計ジャッジ時間 5,122 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>

using namespace std;
const int MAX_N = 100000;
int N;
vector<int> table[MAX_N];

int dp1[MAX_N]; // iをwhiteにするとき, 部分木iで黒は最大いくつ塗れるか
int dp2[MAX_N]; // iをblackにするとき, 部分木iでは黒は最大いくつ塗れるか
// 黒は連続して塗らない.
// 葉以外に塗られた黒の個数の最大値

void dfs(int node, int par) {
    int s1 = 0;
    int s2 = 1;
    
    for (int next : table[node]) {
        if (node == par) continue;
        dfs(next, node);
        
        s1 += max(dp1[next], dp2[next]);
        s2 += dp1[next];
    }
    
    dp1[node] = s1;
    dp2[node] = s2;
}

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N - 1; i++) {
        int s, t;
        cin >> s >> t;
        s--; t--;
        table[s].push_back(t);
        table[t].push_back(s);
    }
    dfs(0, -1);
    cout << max(dp1[0], dp2[0]) << endl;
}
0