結果

問題 No.763 Noelちゃんと木遊び
ユーザー te-sh
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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); }
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0