結果

問題 No.922 東北きりきざむたん
ユーザー roaris
提出日時 2020-12-02 15:20:23
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 722 ms / 2,000 ms
コード長 4,010 bytes
コンパイル時間 299 ms
コンパイル使用メモリ 82,604 KB
実行使用メモリ 120,416 KB
最終ジャッジ日時 2025-03-26 14:13:49
合計ジャッジ時間 13,062 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
input = sys.stdin.readline
from collections import *

class Unionfind:
    def __init__(self, n):
        self.par = [-1]*n
        self.rank = [1]*n
    
    def root(self, x):
        r = x
        
        while not self.par[r]<0:
            r = self.par[r]
        
        t = x
        
        while t!=r:
            tmp = t
            t = self.par[t]
            self.par[tmp] = r
        
        return r
    
    def unite(self, x, y):
        rx = self.root(x)
        ry = self.root(y)
        
        if rx==ry:
            return
        
        if self.rank[rx]<=self.rank[ry]:
            self.par[ry] += self.par[rx]
            self.par[rx] = ry
            
            if self.rank[rx]==self.rank[ry]:
                self.rank[ry] += 1
        else:
            self.par[rx] += self.par[ry]
            self.par[ry] = rx
    
    def is_same(self, x, y):
        return self.root(x)==self.root(y)
    
    def count(self, x):
        return -self.par[self.root(x)]

class LCA:
    def __init__(self, N, G):
        self.N = N
        self.G = G
        self.log_size = 22
        self.par = [[-1]*self.N for _ in range(self.log_size)]
        self.dep = [-1]*self.N
        
        for i in range(self.N):
            if self.dep[i]==-1:
                self.dep[i] = 0
                q = deque([i])
                
                while q:
                    v = q.popleft()
                    
                    for nv in self.G[v]:
                        if self.dep[nv]==-1:
                            self.par[0][nv] = v
                            self.dep[nv] = self.dep[v]+1
                            q.append(nv)
                    
        for i in range(1, self.log_size):
            for v in range(self.N):
                if self.par[i-1][v]>=0:
                    self.par[i][v] = self.par[i-1][self.par[i-1][v]]
        
    def lca(self, u, v):
        if self.dep[u]>self.dep[v]:
            u, v = v, u
        
        for i in range(self.log_size):
            if ((self.dep[v]-self.dep[u])>>i)&1:
                v = self.par[i][v]
        
        if u==v:
            return u
        
        for i in range(self.log_size-1, -1, -1):
            if self.par[i][u]!=self.par[i][v]:
                u, v = self.par[i][u], self.par[i][v]
        
        return self.par[0][u]
    
    def dist(self, u, v):
        return self.dep[u]+self.dep[v]-2*self.dep[self.lca(u, v)]

def dfs1(s):
    in_order_now = 0
    stack = [(s, -1, 0)]
    total_d = 0
    vs = []
    
    while stack:
        v, pv, d = stack.pop()
        
        in_order[v] = in_order_now
        in_order_now += 1
        total_d += cnt[v]*d
        vs.append((in_order[v], v))
        
        for nv in G[v]:
            if nv==pv:
                continue
            
            par[nv] = v
            stack.append((nv, v, d+1))
    
    vs.sort(reverse=True)
    
    for _, v in vs:
        if v==s:
            continue
        
        cnt[par[v]] += cnt[v]
    
    return total_d
    
def dfs2(s, total_d):
    stack = [(s, -1, total_d)]
    res = total_d
    
    while stack:
        v, pv, total_d = stack.pop()
        
        for nv in G[v]:
            if nv==pv:
                continue
            
            next_d = total_d+cnt[s]-2*cnt[nv]
            res = min(res, next_d)
            stack.append((nv, v, next_d))
    
    return res
    
N, M, Q = map(int, input().split())
uf = Unionfind(N)
G = [[] for _ in range(N)]

for _ in range(M):
    u, v = map(int, input().split())
    uf.unite(u-1, v-1)
    G[u-1].append(v-1)
    G[v-1].append(u-1)

lc = LCA(N, G)
ans = 0
cnt = [0]*N

for _ in range(Q):
    a, b = map(int, input().split())
    
    if uf.is_same(a-1, b-1):
        ans += lc.dist(a-1, b-1)
    else:
        cnt[a-1] += 1
        cnt[b-1] += 1

rs = set()

for i in range(N):
    r = uf.root(i)
    rs.add(r)

par = [-1]*N
in_order = [-1]*N

for r in rs:
    total_d = dfs1(r)
    ans += dfs2(r, total_d)
    
print(ans)
0