結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー | hashiryo |
提出日時 | 2020-05-17 23:26:10 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 56 ms / 2,000 ms |
コード長 | 2,645 bytes |
コンパイル時間 | 1,987 ms |
コンパイル使用メモリ | 180,672 KB |
実行使用メモリ | 19,072 KB |
最終ジャッジ日時 | 2024-10-01 12:38:14 |
合計ジャッジ時間 | 4,318 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 39 ms
19,072 KB |
testcase_01 | AC | 16 ms
6,820 KB |
testcase_02 | AC | 41 ms
11,264 KB |
testcase_03 | AC | 27 ms
8,576 KB |
testcase_04 | AC | 20 ms
7,168 KB |
testcase_05 | AC | 23 ms
8,448 KB |
testcase_06 | AC | 50 ms
12,928 KB |
testcase_07 | AC | 56 ms
12,672 KB |
testcase_08 | AC | 27 ms
8,832 KB |
testcase_09 | AC | 18 ms
7,040 KB |
testcase_10 | AC | 8 ms
5,248 KB |
testcase_11 | AC | 52 ms
13,184 KB |
testcase_12 | AC | 44 ms
12,032 KB |
testcase_13 | AC | 43 ms
11,904 KB |
testcase_14 | AC | 37 ms
11,008 KB |
testcase_15 | AC | 27 ms
8,704 KB |
testcase_16 | AC | 5 ms
5,248 KB |
testcase_17 | AC | 27 ms
8,576 KB |
testcase_18 | AC | 50 ms
13,056 KB |
testcase_19 | AC | 41 ms
12,160 KB |
testcase_20 | AC | 42 ms
12,160 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; #define debug(x) cerr << #x << ": " << x << endl #define debugArray(x, n) \ for (long long hoge = 0; (hoge) < (n); ++(hoge)) \ cerr << #x << "[" << hoge << "]: " << x[hoge] << endl template <typename T, typename E> struct Tree_DP { struct Edge { int to; E data; T dp, ndp; }; using F = function<T(T, T)>; using G1 = function<T(T, E)>; using G2 = function<T(T, int)>; private: vector<vector<Edge>> graph; vector<T> subdp, dp; const T init; const F f; const G1 g1; const G2 g2; private: void dfs_sub(int idx, int par) { for (auto &e : graph[idx]) { if (e.to == par) continue; dfs_sub(e.to, idx); subdp[idx] = f(subdp[idx], g1(subdp[e.to], e.data)); } subdp[idx] = g2(subdp[idx], idx); } void dfs_all(int idx, int par, const T &top) { T buff{init}; for (int i = 0; i < (int)graph[idx].size(); i++) { auto &e = graph[idx][i]; e.ndp = buff; e.dp = g1(par == e.to ? top : subdp[e.to], e.data); buff = f(buff, e.dp); } dp[idx] = g2(buff, idx); buff = init; for (int i = (int)graph[idx].size() - 1; i >= 0; i--) { auto &e = graph[idx][i]; if (e.to != par) dfs_all(e.to, idx, f(e.ndp, buff)); e.ndp = f(e.ndp, buff); buff = f(buff, e.dp); } } public: Tree_DP(int V, const F f, const G1 g1, const G2 g2, T init) : graph(V), f(f), g1(g1), g2(g2), init(init), subdp(V, init), dp(V, init) {} void add_edge(int u, int v, E d, E e) { graph[u].emplace_back((Edge){v, d, init, init}); graph[v].emplace_back((Edge){u, e, init, init}); } void add_edge(int u, int v, E d = E()) { add_edge(u, v, d, d); } T build(int root) { dfs_sub(root, -1); return subdp[root]; } vector<T> build_rerooting() { dfs_sub(0, -1); dfs_all(0, -1, init); return dp; } }; signed main() { cin.tie(0); ios::sync_with_stdio(0); int N; cin >> N; using Pii = pair<int, int>; auto f = [](const Pii &vdp, const Pii &chdp) { Pii ret = vdp; ret.first += max(chdp.first - 1, chdp.second); ret.second += max(chdp.first, chdp.second); return ret; }; auto g1 = [](const Pii &dp, int dat) { return dp; }; auto g2 = [](const Pii &dp, int v) { return Pii{dp.first + 1, dp.second}; }; Tree_DP<Pii, int> graph(N, f, g1, g2, {0, 0}); for (int i = 0; i < N - 1; i++) { int u, v; cin >> u >> v; u--, v--; graph.add_edge(u, v); } auto ans = graph.build(0); cout << max(ans.first, ans.second) << endl; return 0; }