結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー | hashiryo |
提出日時 | 2020-05-17 23:41:26 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 44 ms / 2,000 ms |
コード長 | 2,386 bytes |
コンパイル時間 | 1,958 ms |
コンパイル使用メモリ | 178,492 KB |
実行使用メモリ | 17,024 KB |
最終ジャッジ日時 | 2024-10-01 13:01:31 |
合計ジャッジ時間 | 3,928 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 38 ms
17,024 KB |
testcase_01 | AC | 16 ms
6,656 KB |
testcase_02 | AC | 39 ms
11,264 KB |
testcase_03 | AC | 23 ms
8,576 KB |
testcase_04 | AC | 18 ms
7,168 KB |
testcase_05 | AC | 23 ms
8,576 KB |
testcase_06 | AC | 43 ms
12,928 KB |
testcase_07 | AC | 37 ms
12,672 KB |
testcase_08 | AC | 23 ms
8,832 KB |
testcase_09 | AC | 15 ms
6,912 KB |
testcase_10 | AC | 7 ms
5,248 KB |
testcase_11 | AC | 44 ms
13,056 KB |
testcase_12 | AC | 37 ms
11,904 KB |
testcase_13 | AC | 36 ms
11,904 KB |
testcase_14 | AC | 31 ms
10,880 KB |
testcase_15 | AC | 22 ms
8,704 KB |
testcase_16 | AC | 5 ms
5,248 KB |
testcase_17 | AC | 24 ms
8,832 KB |
testcase_18 | AC | 42 ms
13,056 KB |
testcase_19 | AC | 35 ms
12,160 KB |
testcase_20 | AC | 36 ms
12,032 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 G = function<T(T, E)>; private: vector<vector<Edge>> graph; vector<T> subdp, dp; const T init; const F f; const G g; 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], g(subdp[e.to], e.data)); } } 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 = g(par == e.to ? top : subdp[e.to], e.data); buff = f(buff, e.dp); } dp[idx] = buff; 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 G g, T init) : graph(V), f(f), g(g), 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 g = [](const Pii &dp, int dat) { return dp; }; Tree_DP<Pii, int> graph(N, f, g, {1, 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; }