結果

問題 No.763 Noelちゃんと木遊び
ユーザー kkktymkkktym
提出日時 2020-04-30 15:54:26
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 83 ms
16,868 KB
testcase_01 AC 33 ms
7,012 KB
testcase_02 AC 79 ms
11,284 KB
testcase_03 AC 53 ms
8,720 KB
testcase_04 AC 38 ms
7,216 KB
testcase_05 AC 50 ms
8,576 KB
testcase_06 AC 99 ms
13,072 KB
testcase_07 AC 94 ms
12,768 KB
testcase_08 AC 54 ms
9,024 KB
testcase_09 AC 37 ms
6,928 KB
testcase_10 AC 15 ms
5,248 KB
testcase_11 AC 102 ms
13,236 KB
testcase_12 AC 93 ms
12,288 KB
testcase_13 AC 87 ms
12,012 KB
testcase_14 AC 78 ms
10,980 KB
testcase_15 AC 51 ms
8,704 KB
testcase_16 AC 10 ms
5,248 KB
testcase_17 AC 51 ms
8,680 KB
testcase_18 AC 105 ms
13,092 KB
testcase_19 AC 90 ms
12,176 KB
testcase_20 AC 89 ms
12,324 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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 node
  vector<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;
}
0