結果

問題 No.768 Tapris and Noel play the game on Treeone
コンテスト
ユーザー pekempey
提出日時 2018-12-16 02:23:53
言語 C++14
(gcc 15.2.0 + boost 1.89.0)
コンパイル:
g++-15 -O2 -lm -std=c++14 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 1,465 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 602 ms
コンパイル使用メモリ 99,292 KB
実行使用メモリ 9,224 KB
最終ジャッジ日時 2026-04-12 10:45:38
合計ジャッジ時間 2,521 ms
ジャッジサーバーID
（参考情報） 		judge1_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 2
other AC * 1 WA * 21
権限があれば一括ダウンロードができます
コンパイルメッセージ
In file included from /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/vector:69,
                 from main.cpp:3:
In member function 'std::_Bit_reference& std::_Bit_reference::operator=(bool)',
    inlined from 'free_tree_dp<bool, main()::<lambda(bool, bool)>, main()::<lambda(bool)> >(const std::vector<std::vector<int> >&, main()::<lambda(bool, bool)>, main()::<lambda(bool)>)::<lambda(int, int)>' at main.cpp:41:9,
    inlined from 'constexpr _Res std::__invoke_impl(__invoke_other, _Fn&&, _Args&& ...) [with _Res = void; _Fn = free_tree_dp<bool, main()::<lambda(bool, bool)>, main()::<lambda(bool)> >(const std::vector<std::vector<int> >&, main()::<lambda(bool, bool)>, main()::<lambda(bool)>)::<lambda(int, int)>&; _Args = {int, int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/invoke.h:63:36,
    inlined from 'constexpr std::__enable_if_t<((bool)std::is_void< <template-parameter-1-1> >::value), _Res> std::__invoke_r(_Callable&&, _Args&& ...) [with _Res = void; _Callable = free_tree_dp<bool, main()::<lambda(bool, bool)>, main()::<lambda(bool)> >(const std::vector<std::vector<int> >&, main()::<lambda(bool, bool)>, main()::<lambda(bool)>)::<lambda(int, int)>&; _Args = {int, int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/invoke.h:152:33,
    inlined from 'static _Res std::_Function_handler<_Res(_ArgTypes ...), _Functor>::_M_invoke(const std::_Any_data&, _ArgTypes&& ...) [with _Res = void; _Functor = free_tree_dp<bool, main()::<lambda(bool, bool)>, main()::<lambda(bool)> >(const std::vector<std::vector<int> >&, main()::<lambda(bool, bool)>, main()::<lambda(bool)>)::<lambda(int, int)>; _ArgTypes = {int, int}]' at /home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/std_function.h:292:30:
/home/linuxbrew/.linuxbrew/Cellar/gcc/15.2.0_1/include/c++/15/bits/stl_bvector.h:112:7: warning: 'l' may be used uninitialized [-Wmaybe-uninitialized]
  112 |       if (__x)
      |       ^~
main.cpp: In sta

ソースコード

diff #
raw source code 

#include <iostream>
#include <algorithm>
#include <vector>
#include <functional>

using namespace std;

// add :: T -> T -> T
//     {v1,v2,...,vm}+vm+1
// bundle :: T -> T
//     u->{v1,v2,v3,...,vm} 
template<class T, class F1, class F2>
vector<T> free_tree_dp(const vector<vector<int>> &g, F1 add, F2 bundle) {
	const int n = g.size();
	vector<T> dp(n);
	function<void(int, int)> dfs = [&](int u, int p) {
		for (int v : g[u]) {
			if (v != p) {
				dfs(v, u);
				dp[u] = add(dp[u], dp[v]);
			}
		}
		dp[u] = bundle(dp[u]);
	};
	dfs(0, -1);
	function<void(int, int)> dfs2 = [&](int u, int p) {
		const int m = g[u].size();
		T l;
		vector<T> r(m);
		for (int i = m - 2; i >= 0; i--) {
			r[i] = add(dp[g[u][i + 1]], r[i + 1]);
		}
		for (int i = 0; i < m; i++) {
			const int v = g[u][i];
			dp[u] = bundle(add(l, r[i]));
			l = add(l, dp[v]);
			if (v != p) {
				dfs2(v, u);
			}
		}
		dp[u] = bundle(l);
	};
	dfs2(0, -1);
	return dp;
}

int main() {
	int n;
	cin >> n;
	vector<vector<int>> g(n);
	for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
		u--;
		v--;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	auto add = [&](bool a, bool b) {
        return a || b;
	};
	auto bundle = [&](bool a) {
        return !a;
	};
    auto dp = free_tree_dp<bool>(g, add, bundle);
    cout << count(dp.begin(), dp.end(), true) << endl;
    for (int i = 0; i < n; i++) {
        if (dp[i]) {
            cout << i + 1 << endl;
        }
    }
}
0