結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
|
提出日時 | 2020-04-30 15:54:26 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 105 ms / 2,000 ms |
コード長 | 2,339 bytes |
コンパイル時間 | 1,048 ms |
コンパイル使用メモリ | 82,476 KB |
実行使用メモリ | 16,868 KB |
最終ジャッジ日時 | 2024-12-15 23:57:48 |
合計ジャッジ時間 | 4,266 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>#define rep(i,n) for(int i=0;i<n;++i)#define rep1(i,n) for(int i=1;i<=n;++i)using namespace std;template<class T>bool chmax(T &a, const T &b) { if(a < b){ a = b; return 1; } return 0; }template<class T>bool chmin(T &a, const T &b) { if(a > b){ a = b; return 1; } return 0; }template <typename X>struct Edge{int from;int to;X cost;Edge() = default;Edge(int from, int to, X cost) : from(from), to(to), cost(cost) {}};template <typename X>struct Node{int idx;int par;X depth;int dp[2];vector<Edge<X>> edge;Node() = default;explicit Node(int idx) : idx(idx) {rep(i,2) dp[i] = 0;}};template <typename X>class Tree{private:int n; // number of nodevector<Node<X>> node;public:Tree() = default;Tree(int n) : n(n) {rep(i,n) node.emplace_back(i);}Tree(int n, vector<int> a, vector<int> b) : n(n) {rep(i,n) node.emplace_back(i);rep(i,n-1) {add_edge(a[i], b[i]);add_edge(b[i], a[i]); // indirected edge}}Tree(int n, vector<int> a, vector<int> b, vector<X> c) : n(n) {rep(i,n) node.emplace_back(i);rep(i,n-1) {add_edge(a[i], b[i], c[i]);add_edge(b[i], a[i], c[i]); // indirected edge}}void add_edge(int from, int to, X cost = 1) {node[from].edge.emplace_back(from, to, cost);}void DFS_Init(int v, int p, int d) {node[v].par = p;node[v].depth = d;for(auto next: node[v].edge) {int w = next.to;X cost = next.cost;if(w == p) continue;DFS_Init(w, v, d + cost);}}void Init_Node(int root) {DFS_Init(root, -1, 0);}int DFS(int v, int color) {if(node[v].dp[color] > 0) return node[v].dp[color];int res;if(color == 0) res = 0;else res = 1;for(auto next: node[v].edge) {int w = next.to;if(w == node[v].par) continue;if(color == 0) {res += max(DFS(w, 0), DFS(w, 1));}else {res += DFS(w, 0);}}return node[v].dp[color] = res;}};int main(){int n;cin >> n;vector<int> a(n-1), b(n-1);rep(i,n-1) {cin >> a[i] >> b[i];a[i]--; b[i]--;}Tree<int> tr(n, a, b);tr.Init_Node(0);cout << max(tr.DFS(0, 0), tr.DFS(0, 1)) << "\n";return 0;}