結果
問題 | No.2892 Lime and Karin |
ユーザー |
![]() |
提出日時 | 2024-09-13 23:04:05 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,421 bytes |
コンパイル時間 | 254 ms |
コンパイル使用メモリ | 82,224 KB |
実行使用メモリ | 198,984 KB |
最終ジャッジ日時 | 2024-09-13 23:04:17 |
合計ジャッジ時間 | 11,472 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 11 TLE * 1 |
ソースコード
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 = Nonewhile True:y = next((y for y in G[x] if not used[y] and y != p and size[y] * 2 > size[x]), 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 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)d.sort()# d[i] + d[j] + S[u] > 0val -= sum(len(d) - bisect_left(d, -x - S[u] + 1) for x in d)ds.extend(d)ds.sort()val += sum(len(ds) - bisect_left(ds, -x - S[u] + 1) for x in ds)ans += val // 2used[u] = Trueprint(ans)