結果
問題 |
No.1418 Sum of Sum of Subtree Size
|
ユーザー |
👑 |
提出日時 | 2021-07-22 00:22:30 |
言語 | Lua (LuaJit 2.1.1734355927) |
結果 |
AC
|
実行時間 | 199 ms / 2,000 ms |
コード長 | 1,140 bytes |
コンパイル時間 | 117 ms |
コンパイル使用メモリ | 6,940 KB |
実行使用メモリ | 20,736 KB |
最終ジャッジ日時 | 2024-07-17 14:27:37 |
合計ジャッジ時間 | 3,956 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
local n = io.read("*n") local edge = {} local parent = {} local childcnt = {} local w = {} local asked = {} for i = 1, n do edge[i] = {} parent[i] = 0 childcnt[i] = 0 w[i] = 1 asked[i] = false end for i = 1, n - 1 do local p, q = io.read("*n", "*n") table.insert(edge[p], q) table.insert(edge[q], p) end local tasks = {1} asked[1] = true for i = 1, n do local src = tasks[i] for j = 1, #edge[src] do local dst = edge[src][j] if not asked[dst] then asked[dst] = true childcnt[src] = childcnt[src] + 1 table.insert(tasks, dst) parent[dst] = src end end end local ret = n * n tasks = {} for i = 1, n do if childcnt[i] == 0 then table.insert(tasks, i) end end for i = 1, n do local src = tasks[i] ret = ret + (n - w[src]) * w[src] local p = parent[src] for j = 1, #edge[src] do local dst = edge[src][j] if dst ~= p then ret = ret + w[dst] * (n - w[dst]) end end if 0 < p then childcnt[p] = childcnt[p] - 1 if childcnt[p] == 0 then table.insert(tasks, p) end w[p] = w[p] + w[src] end end ret = tostring(1LL * ret):gsub("LL", "") print(ret)