結果

問題 No.763 Noelちゃんと木遊び
ユーザー te-shte-sh
提出日時 2018-12-11 12:34:49
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 181 ms / 2,000 ms
コード長 2,191 bytes
コンパイル時間 1,068 ms
コンパイル使用メモリ 111,492 KB
実行使用メモリ 16,376 KB
最終ジャッジ日時 2024-06-13 02:13:24
合計ジャッジ時間 4,854 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 113 ms
14,044 KB
testcase_01 AC 53 ms
9,108 KB
testcase_02 AC 146 ms
13,524 KB
testcase_03 AC 95 ms
14,032 KB
testcase_04 AC 61 ms
9,708 KB
testcase_05 AC 86 ms
11,920 KB
testcase_06 AC 178 ms
14,740 KB
testcase_07 AC 176 ms
14,372 KB
testcase_08 AC 96 ms
13,228 KB
testcase_09 AC 60 ms
9,880 KB
testcase_10 AC 24 ms
6,940 KB
testcase_11 AC 181 ms
16,376 KB
testcase_12 AC 161 ms
13,608 KB
testcase_13 AC 153 ms
13,500 KB
testcase_14 AC 136 ms
13,108 KB
testcase_15 AC 88 ms
12,924 KB
testcase_16 AC 14 ms
6,940 KB
testcase_17 AC 93 ms
13,408 KB
testcase_18 AC 180 ms
14,876 KB
testcase_19 AC 162 ms
13,544 KB
testcase_20 AC 162 ms
14,024 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std.algorithm, std.container, std.conv, std.math, std.range, std.typecons, std.stdio, std.string;

auto rdsp(){return readln.splitter;}
void pick(R,T)(ref R r,ref T t){t=r.front.to!T;r.popFront;}
void readV(T...)(ref T t){auto r=rdsp;foreach(ref v;t)pick(r,v);}

void main()
{
  int n; readV(n);

  auto g = Graph!int(n);
  foreach (i; 0..n-1) {
    int u, v; readV(u, v); --u; --v;
    g.addEdgeB(u, v);
  }

  auto t = g.makeTree.rootify(0);

  auto st1 = SList!int(0), st2 = SList!int();
  while (!st1.empty) {
    auto u = st1.front; st1.removeFront();
    st2.insertFront(u);
    foreach (v; t.children(u)) st1.insertFront(v);
  }

  auto a = new int[](n), b = new int[](n);
  while (!st2.empty) {
    auto u = st2.front; st2.removeFront();
    a[u] = 1;
    foreach (v; t.children(u)) {
      a[u] += max(a[v]-1, b[v]);
      b[u] += max(a[v], b[v]);
    }
  }

  writeln(max(a[0], b[0]));
}

struct Graph(N = int)
{
  alias Node = N;
  Node n;
  Node[][] g;
  alias g this;
  this(Node n) { this.n = n; g = new Node[][](n); }
  void addEdge(Node u, Node v) { g[u] ~= v; }
  void addEdgeB(Node u, Node v) { g[u] ~= v; g[v] ~= u; }
}

struct Tree(Graph)
{
  import std.algorithm, std.container;
  alias Node = Graph.Node;
  Graph g;
  alias g this;
  Node root;
  Node[] parent;
  int[] size, depth;

  this(ref Graph g) { this.g = g; this.n = g.n; }

  ref auto rootify(Node r)
  {
    this.root = r;

    parent = new Node[](g.n);
    depth = new int[](g.n);
    depth[] = -1;

    struct UP { Node u, p; }
    auto st1 = SList!UP(UP(r, r));
    auto st2 = SList!UP();
    while (!st1.empty) {
      auto up = st1.front, u = up.u, p = up.p; st1.removeFront();

      parent[u] = p;
      depth[u] = depth[p] + 1;

      foreach (v; g[u])
        if (v != p) {
          st1.insertFront(UP(v, u));
          st2.insertFront(UP(v, u));
        }
    }

    size = new int[](g.n);
    size[] = 1;

    while (!st2.empty) {
      auto up = st2.front, u = up.u, p = up.p; st2.removeFront();
      size[p] += size[u];
    }

    return this;
  }

  auto children(Node u) { return g[u].filter!(v => v != parent[u]); }
}
ref auto makeTree(Graph)(ref Graph g) { return Tree!Graph(g); }
0