結果
| 問題 |
No.922 東北きりきざむたん
|
| ユーザー |
 neterukun
|
| 提出日時 | 2021-01-15 12:33:05 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 887 ms / 2,000 ms |
| コード長 | 6,861 bytes |
| コンパイル時間 | 156 ms |
| コンパイル使用メモリ | 82,396 KB |
| 実行使用メモリ | 172,608 KB |
| 最終ジャッジ日時 | 2024-11-25 10:22:47 |
| 合計ジャッジ時間 | 16,226 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 26 |
ソースコード
class HLDecomposition:
def __init__(self, tree):
self.tree = tree
self.n = len(tree)
self.par = [-1] * self.n
self.size = [1] * self.n
self.depth = [0] * self.n
self.preorder = [0] * self.n
self.head = [i for i in range(self.n)]
self.k = 0
for v in range(self.n):
if self.par[v] == -1:
self.dfs_pre(v)
self.dfs_hld(v)
def __getitem__(self, v):
return self.preorder[v]
def dfs_pre(self, v):
tree = self.tree
stack = [v]
order = [v]
while stack:
v = stack.pop()
for chi_v in tree[v]:
if chi_v == self.par[v]:
continue
self.par[chi_v] = v
self.depth[chi_v] = self.depth[v] + 1
stack.append(chi_v)
order.append(chi_v)
for v in reversed(order):
tree_v = tree[v]
if len(tree_v) and tree_v[0] == self.par[v]:
tree_v[0], tree_v[-1] = tree_v[-1], tree_v[0]
for idx, chi_v in enumerate(tree_v):
if chi_v == self.par[v]:
continue
self.size[v] += self.size[chi_v]
if self.size[chi_v] > self.size[tree_v[0]]:
tree_v[idx], tree_v[0] = tree_v[0], tree_v[idx]
def dfs_hld(self, v):
stack = [v]
while stack:
v = stack.pop()
self.preorder[v] = self.k
self.k += 1
if len(self.tree[v]) == 0:
continue
top = self.tree[v][0]
for chi_v in reversed(self.tree[v]):
if chi_v == self.par[v]:
continue
if chi_v == top:
self.head[chi_v] = self.head[v]
else:
self.head[chi_v] = chi_v
stack.append(chi_v)
def lca(self, u, v):
while u != -1 and v != -1:
if self.preorder[u] > self.preorder[v]:
u, v = v, u
if self.head[u] == self.head[v]:
return u
v = self.par[self.head[v]]
return -1
def distance(self, u, v):
lca_uv = self.lca(u, v)
if lca_uv == -1:
return -1
else:
return self.depth[u] + self.depth[v] - 2 * self.depth[lca_uv]
def range_vertex_path(self, u, v):
while True:
if self.preorder[u] > self.preorder[v]:
u, v = v, u
l = max(self.preorder[self.head[v]], self.preorder[u])
r = self.preorder[v]
yield l, r + 1 # 半開区間
if self.head[u] != self.head[v]:
v = self.par[self.head[v]]
else:
return
def range_edge_path(self, u, v):
while True:
if self.preorder[u] > self.preorder[v]:
u, v = v, u
if self.head[u] != self.head[v]:
yield self.preorder[self.head[v]], self.preorder[v] + 1 # 半開区間
v = self.par[self.head[v]]
else:
if u != v:
yield self.preorder[u] + 1, self.preorder[v] + 1 # 半開区間
break
def range_subtree(self, u):
return self.preorder[u], self.preorder[u] + self.size[u] # 半開区間[l, r)
class UnionFind:
def __init__(self, n):
self.parent = [-1] * n
self.n = n
self.cnt = n
def root(self, x):
if self.parent[x] < 0:
return x
else:
self.parent[x] = self.root(self.parent[x])
return self.parent[x]
def merge(self, x, y):
x = self.root(x)
y = self.root(y)
if x == y:
return False
if self.parent[x] > self.parent[y]:
x, y = y, x
self.parent[x] += self.parent[y]
self.parent[y] = x
self.cnt -= 1
return True
def same(self, x, y):
return self.root(x) == self.root(y)
def size(self, x):
return -self.parent[self.root(x)]
def count(self):
return self.cnt
def groups(self):
res = [[] for _ in range(self.n)]
for i in range(self.n):
res[self.root(i)].append(i)
return [group for group in res if group]
def rerooting(n, edges, unit, merge, addnode):
tree = [[] for i in range(n)]
idxs = [[] for i in range(n)]
for u, v in edges:
idxs[u].append(len(tree[v]))
idxs[v].append(len(tree[u]))
tree[u].append(v)
tree[v].append(u)
sub = [[unit] * len(tree[v]) for v in range(n)]
noderes = [unit] * n
# topological sort
tp_order = []
par = [-1] * n
for root in range(n):
if par[root] != -1:
continue
stack = [root]
while stack:
v = stack.pop()
tp_order.append(v)
for nxt_v in tree[v]:
if nxt_v == par[v]:
continue
par[nxt_v] = v
stack.append(nxt_v)
# tree DP
for v in reversed(tp_order[1:]):
res = unit
par_idx = -1
for idx, nxt_v in enumerate(tree[v]):
if nxt_v == par[v]:
par_idx = idx
continue
res = merge(res, sub[v][idx])
if par_idx != -1:
sub[par[v]][idxs[v][par_idx]] = addnode(res, v)
# rerooting DP
for v in tp_order:
acc_back = [unit] * len(tree[v])
for i in reversed(range(1, len(acc_back))):
acc_back[i - 1] = merge(sub[v][i], acc_back[i])
acc_front = unit
for idx, nxt_v in enumerate(tree[v]):
res = addnode(merge(acc_front, acc_back[idx]), v)
sub[nxt_v][idxs[v][idx]] = res
acc_front = merge(acc_front, sub[v][idx])
noderes[v] = addnode(acc_front, v)
return noderes
n, m, q = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]
queries = [list(map(int, input().split())) for i in range(q)]
tree = [[] for i in range(n)]
uf = UnionFind(n)
for i, (u, v) in enumerate(edges):
u -= 1
v -= 1
tree[u].append(v)
tree[v].append(u)
uf.merge(u, v)
edges[i] = (u, v)
ans = 0
weights = [0] * n
db = HLDecomposition(tree)
for u, v in queries:
u -= 1
v -= 1
dist = db.distance(u, v)
if dist == -1:
weights[u] += 1
weights[v] += 1
else:
ans += dist
unit = (0, 0)
merge = lambda x1, x2: (x1[0] + x2[0], x1[1] + x2[1])
addnode = lambda x1, v: (x1[0] + weights[v], x1[0] + x1[1])
res = rerooting(n, edges, unit, merge, addnode)
for gp in uf.groups():
min_cost = 10 ** 9
for i in gp:
min_cost = min(res[i][1], min_cost)
ans += min_cost
print(ans)