結果

問題 No.763 Noelちゃんと木遊び
ユーザー te-shte-sh
提出日時 2018-12-11 12:34:49
言語 D
(dmd 2.092.1)
結果
AC  
実行時間 186 ms / 2,000 ms
コード長 2,191 Byte
コンパイル時間 1,143 ms
使用メモリ 14,576 KB
最終ジャッジ日時 2020-07-06 19:56:25

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
testcase_00 AC 125 ms
13,524 KB
testcase_01 AC 60 ms
7,980 KB
testcase_02 AC 144 ms
12,728 KB
testcase_03 AC 92 ms
11,672 KB
testcase_04 AC 64 ms
8,772 KB
testcase_05 AC 88 ms
11,412 KB
testcase_06 AC 178 ms
14,316 KB
testcase_07 AC 176 ms
13,784 KB
testcase_08 AC 98 ms
11,936 KB
testcase_09 AC 62 ms
8,508 KB
testcase_10 AC 24 ms
5,072 KB
testcase_11 AC 186 ms
14,576 KB
testcase_12 AC 163 ms
12,992 KB
testcase_13 AC 163 ms
12,992 KB
testcase_14 AC 140 ms
12,728 KB
testcase_15 AC 91 ms
11,672 KB
testcase_16 AC 16 ms
5,068 KB
testcase_17 AC 94 ms
11,672 KB
testcase_18 AC 185 ms
14,316 KB
testcase_19 AC 165 ms
12,992 KB
testcase_20 AC 168 ms
12,992 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