結果

問題 No.399 動的な領主
コンテスト
ユーザー titia
提出日時 2025-12-23 03:32:44
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 455 ms / 2,000 ms
コード長 2,103 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 468 ms
コンパイル使用メモリ 82,400 KB
実行使用メモリ 108,680 KB
最終ジャッジ日時 2025-12-23 03:32:51
合計ジャッジ時間 7,188 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

N=int(input())

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

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

    E[x].append(y)
    E[y].append(x)

# 木のHL分解+LCA

ROOT=0

QUE=[ROOT] 
Parent=[-1]*N
Parent[ROOT]=N # ROOTの親を定めておく.
Child=[[] for i in range(N)]
TOP_SORT=[] # トポロジカルソート

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

Children=[1]*N

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

USE=[0]*N
Group=[i for i in range(N)]

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:
            Group[to]=Group[x]

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

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


Q=int(input())

ANS=[0]*N

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

    lca=LCA(x,y)

    if x==lca:
        ANS[y]+=1
        if x!=0:
            ANS[Parent[x]]-=1
    elif y==lca:
        ANS[x]+=1
        if y!=0:
            ANS[Parent[y]]-=1
    else:
        ANS[x]+=1
        ANS[y]+=1
        ANS[lca]-=1
        if lca!=0:
            ANS[Parent[lca]]-=1

for x in TOP_SORT[::-1]:
    if x!=0:
        ANS[Parent[x]]+=ANS[x]

score=0
for x in ANS:
    score+=x*(x+1)//2

print(score)
0