結果

問題 No.763 Noelちゃんと木遊び
ユーザー te-sh
提出日時 2018-12-11 12:34:49
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 176 ms / 2,000 ms
コード長 2,191 bytes
コンパイル時間 1,085 ms
コンパイル使用メモリ 98,692 KB
実行使用メモリ 15,228 KB
最終ジャッジ日時 2025-03-22 10:33:12
合計ジャッジ時間 4,289 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

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