結果

問題 No.763 Noelちゃんと木遊び
ユーザー te-shte-sh
提出日時 2018-12-11 12:34:49
言語 D
(dmd 2.107.1)
結果
AC  
実行時間 185 ms / 2,000 ms
コード長 2,191 bytes
コンパイル時間 1,665 ms
コンパイル使用メモリ 98,984 KB
実行使用メモリ 15,512 KB
最終ジャッジ日時 2023-09-03 21:34:03
合計ジャッジ時間 4,548 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 124 ms
14,380 KB
testcase_01 AC 56 ms
11,552 KB
testcase_02 AC 147 ms
13,656 KB
testcase_03 AC 93 ms
13,484 KB
testcase_04 AC 63 ms
11,840 KB
testcase_05 AC 87 ms
13,448 KB
testcase_06 AC 178 ms
15,276 KB
testcase_07 AC 174 ms
15,424 KB
testcase_08 AC 101 ms
13,192 KB
testcase_09 AC 60 ms
9,556 KB
testcase_10 AC 24 ms
4,844 KB
testcase_11 AC 184 ms
15,512 KB
testcase_12 AC 162 ms
13,928 KB
testcase_13 AC 155 ms
13,948 KB
testcase_14 AC 147 ms
13,712 KB
testcase_15 AC 95 ms
13,444 KB
testcase_16 AC 15 ms
4,384 KB
testcase_17 AC 92 ms
12,908 KB
testcase_18 AC 185 ms
15,292 KB
testcase_19 AC 167 ms
13,976 KB
testcase_20 AC 166 ms
13,932 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