結果

問題 No.922 東北きりきざむたん
コンテスト
ユーザー titia
提出日時 2025-12-29 03:38:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 894 ms / 2,000 ms
コード長 4,067 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 282 ms
コンパイル使用メモリ 82,896 KB
実行使用メモリ 127,076 KB
最終ジャッジ日時 2025-12-29 03:38:43
合計ジャッジ時間 16,308 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

from collections import deque

N,M,Q=map(int,input().split())

# UnionFind

Group = [i for i in range(N)] # グループ分け
Nodes = [1]*(N) # 各グループのノードの数

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

def Union(x,y):
    if find(x) != find(y):
        if Nodes[find(x)] < Nodes[find(y)]:
            
            Nodes[find(y)] += Nodes[find(x)]
            Nodes[find(x)] = 0
            Group[find(x)] = find(y)
            
        else:
            Nodes[find(x)] += Nodes[find(y)]
            Nodes[find(y)] = 0
            Group[find(y)] = find(x)

E=[[] for i in range(N)]

for i in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1
    E[x].append(y)
    E[y].append(x)

    Union(x,y)

A=[0]*N

QU=[[] for i in range(N)]
for i in range(Q):
    x,y=map(int,input().split())
    x-=1
    y-=1

    if find(x)==find(y):
        QU[find(x)].append((x,y))
    else:
        A[x]+=1
        A[y]+=1

F=[[] for i in range(N)]

for i in range(N):
    F[find(i)].append(i)

Parent=[-1]*N
Child=[[] for i in range(N)]
Children=[1]*N
USE=[0]*N
Group2=[i for i in range(N)]
ANS=0
DIS=[1<<60]*N
WS=[0]*N
Childind=[0]*N

for i in range(N):
    if find(i)==i:
        # 木のHL分解+LCA

        ROOT=i
        QUE=[ROOT] 
        Parent[ROOT]=N # ROOTの親を定めておく.
        TOP_SORT=[] # トポロジカルソート
        DIS[ROOT]=0

        while QUE: # トポロジカルソートと同時に親を見つける
            x=QUE.pop()
            TOP_SORT.append(x)
            for to in E[x]:
                if Parent[to]==-1:
                    Parent[to]=x
                    DIS[to]=DIS[x]+1
                    Child[x].append(to)
                    QUE.append(to)


        for x in TOP_SORT[::-1]: #（自分を含む）子ノードの数を調べる
            if x==ROOT:
                break
            Children[Parent[x]]+=Children[x]

        for x in TOP_SORT: # HL分解によるグループ分け
            USE[x]=1
            MAX_children=0
            select_node=0

            for to in E[x]:
                if USE[to]==0 and Children[to]>MAX_children:
                    select_node=to
                    MAX_children=Children[to]

            for to in E[x]:
                if USE[to]==0 and to==select_node:
                    Group2[to]=Group2[x]

        def LCA(a,b): # HL分解を利用してLCAを求める
            while Group2[a]!=Group2[b]:
                if Group2[b]==ROOT:
                    a=Parent[Group2[a]]
                elif Group2[a]==ROOT:
                    b=Parent[Group2[b]]
                elif Children[Parent[Group2[a]]]<Children[Parent[Group2[b]]]:
                    a=Parent[Group2[a]]
                else:
                    b=Parent[Group2[b]]

            if Children[a]>Children[b]:
                return a
            else:
                return b

        for x,y in QU[ROOT]:
            lca=LCA(x,y)
            dx=DIS[x]
            dy=DIS[y]
            dl=DIS[lca]

            if x==lca or y==lca:
                ANS+=abs(dx-dy)
            else:
                ANS+=abs(dx-dl)
                ANS+=abs(dy-dl)

        now=0
        SUM=0
        for x in F[ROOT]:
            now+=DIS[x]*A[x]
            WS[x]+=A[x]
            SUM+=A[x]

        scoremin=now

        for x in TOP_SORT[::-1]:
            for c in Child[x]:
                WS[x]+=WS[c]

        nowind=ROOT

        while True:
            if nowind==N:
                break
            if Childind[nowind]==len(Child[nowind]):

                kk=WS[nowind]
                now+=kk-(SUM-kk)
                nowind=Parent[nowind]

                
            else:
                Childind[nowind]+=1
                toind=Child[nowind][Childind[nowind]-1]

                kk=WS[toind]
                now+=(SUM-kk)-kk

                nowind=toind

            scoremin=min(scoremin,now)

        ANS+=scoremin

                

print(ANS)
0