結果
問題 | No.763 Noelちゃんと木遊び |
ユーザー |
|
提出日時 | 2018-12-11 12:34:49 |
言語 | D (dmd 2.109.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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
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); }