結果

問題 No.763 Noelちゃんと木遊び
ユーザー nanae
提出日時 2018-12-11 10:22:13
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 108 ms / 2,000 ms
コード長 1,532 bytes
コンパイル時間 832 ms
コンパイル使用メモリ 106,204 KB
実行使用メモリ 33,024 KB
最終ジャッジ日時 2024-06-13 02:13:02
合計ジャッジ時間 3,589 ms
ジャッジサーバーID
(参考情報)
judge1 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

import std.stdio, std.string, std.conv;
import std.range, std.algorithm, std.array, std.typecons, std.container;
import std.math, std.numeric, core.bitop;
enum mod = 10^^9 + 7;
void main() {
int n;
scan(n);
auto adj = new int[][](n, 0);
foreach (i ; 0 .. n - 1) {
int ui, vi;
scan(ui, vi);
ui--, vi--;
adj[ui] ~= vi;
adj[vi] ~= ui;
}
auto dp = new int[][](n, 2);
fillAll(dp, -1);
void dfs(int p, int v) {
if (dp[v][0] != -1) {
return;
}
int allDelete;
dp[v][0] = 0;
foreach (u ; adj[v]) {
if (u == p) {
continue;
}
dfs(v, u);
allDelete += dp[u][0];
dp[v][0] += max(dp[u][0], dp[u][1]);
}
dp[v][1] = max(dp[v][0], allDelete + 1);
}
dfs(-1, 0);
debug {
writefln("%(%s\n%)", dp);
}
writeln(max(dp[0][0], dp[0][1]));
}
void scan(T...)(ref T args) {
import std.stdio : readln;
import std.algorithm : splitter;
import std.conv : to;
import std.range.primitives;
auto line = readln().splitter();
foreach (ref arg; args) {
arg = line.front.to!(typeof(arg));
line.popFront();
}
assert(line.empty);
}
void fillAll(R, T)(ref R arr, T value) {
static if (is(typeof(arr[] = value))) {
arr[] = value;
}
else {
foreach (ref e; arr) {
fillAll(e, value);
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0