結果
問題 | No.2892 Lime and Karin |
ユーザー |
![]() |
提出日時 | 2024-09-13 23:12:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,302 ms / 8,000 ms |
コード長 | 1,446 bytes |
コンパイル時間 | 308 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 130,760 KB |
最終ジャッジ日時 | 2024-09-13 23:13:23 |
合計ジャッジ時間 | 63,500 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 52 |
ソースコード
from bisect import bisect_leftN = int(input())G = [[] for _ in range(N)]for _ in range(N - 1):u, v = [int(x) - 1 for x in input().split()]G[u].append(v)G[v].append(u)S = [1 if x == '1' else -1 for x in input()]used = [False] * Nsize = [0] * Ndef centroid(x):stk = [(x, None, 0)]while stk:u, p, t = stk.pop()if t == 0:stk.append((u, p, 1))for v in G[u]:if not used[v] and v != p:stk.append((v, u, 0))else:size[u] = 1 + sum(size[v] for v in G[u] if not used[v] and v != p)p = Nones = size[x]while True:y = next((y for y in G[x] if not used[y] and y != p and size[y] * 2 > s), None)if y is None: breakx, p = y, xreturn xdef totals(x, p):stk = [(x, p, S[x])]res = []while stk:u, p, d = stk.pop()res.append(d)for v in G[u]:if not used[v] and v != p:stk.append((v, u, d + S[v]))return resdef f(xs, y):xs.sort()res = 0i = len(xs)for x in xs:while i >= 1 and x + xs[i - 1] + y > 0:i -= 1res += len(xs) - ireturn resstk = [0]ans = 0while stk:u = centroid(stk.pop())ds = []val = 0if S[u] == 1: ans += 1for v in G[u]:if used[v]: continuestk.append(v)d = totals(v, u)ans += sum(x + S[u] > 0 for x in d)val -= f(d, S[u])ds.extend(d)val += f(ds, S[u])ans += val // 2used[u] = Trueprint(ans)