結果

問題 No.399 動的な領主
ユーザー N-noa21N-noa21
提出日時 2024-08-15 16:48:46
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 472 ms / 2,000 ms
コード長 3,293 bytes
コンパイル時間 126 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 174,376 KB
最終ジャッジ日時 2024-08-15 16:48:52
合計ジャッジ時間 5,954 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 31 ms
53,084 KB
testcase_01 AC 31 ms
54,016 KB
testcase_02 AC 35 ms
55,632 KB
testcase_03 AC 37 ms
54,056 KB
testcase_04 AC 80 ms
76,636 KB
testcase_05 AC 169 ms
80,328 KB
testcase_06 AC 424 ms
97,280 KB
testcase_07 AC 414 ms
96,164 KB
testcase_08 AC 404 ms
95,068 KB
testcase_09 AC 394 ms
95,396 KB
testcase_10 AC 89 ms
77,116 KB
testcase_11 AC 124 ms
79,444 KB
testcase_12 AC 334 ms
96,496 KB
testcase_13 AC 356 ms
96,880 KB
testcase_14 AC 337 ms
174,376 KB
testcase_15 AC 347 ms
173,124 KB
testcase_16 AC 351 ms
140,524 KB
testcase_17 AC 472 ms
96,868 KB
testcase_18 AC 401 ms
95,800 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(2*10**5)
class HeavyLightDecomposition:#N,edge
    def __init__(self,n,edge):
        self.n=n
        self.size=[1]*n
        self.par=[-1]*n

        que=[0]
        while que:#親とこの数を数える段階
            v=que.pop()
            if v>=0:#向かう点が0以上なら木を下る、0未満なら木を登る、下る際には今見ている辺の上向き、下向きを準備して親を定義する
                for u in edge[v]:
                    if u!=self.par[v]:
                        que.append(~u)
                        que.append(u)
                        self.par[u]=v
            else:#上向きではこの数を伝搬する
                v=~v
                self.size[self.par[v]]+=self.size[v]

        self.head=[-1]*n#heavy辺上なら連結しているなかで一番上に位置する点
        self.head[0]=0
        self.order=[-1]*n#振り直された番号
        self.heavy_child=[-1]*n#自分とheavy辺を張られた子

        que=[0]
        cnt=0
        while que:
            v=que.pop()
            self.order[v]=cnt
            cnt+=1
            mx=0
            for u in edge[v]:#heavy辺を決める
                if u!=self.par[v] and mx<self.size[u]:
                    mx=self.size[u]
                    self.heavy_child[v]=u

            for u in edge[v]:#light辺なのでheadは自分自身   
                if self.par[v]!=u and self.heavy_child[v]!=u:
                    self.head[u]=u
                    que.append(u)

            if self.heavy_child[v]!=-1:
                self.head[self.heavy_child[v]]=self.head[v]
                que.append(self.heavy_child[v])
    
    def decomposition(self,u,v):#HL分解により処理された辺を返す
        paths=[]
        while True:
            if self.order[u]>self.order[v]:
                u,v=v,u
            if self.head[u]!=self.head[v]:#自分を含むheavy辺が同じ
                paths.append((self.order[self.head[v]],self.order[v]+1))
                v=self.par[self.head[v]]
            else:
                paths.append((self.order[u]+1,self.order[v]+1))
                tmp = self.lca(u,v)
               # print("aaaa",tmp,self.head[u])
                paths.append((tmp,tmp+1))
                return paths
    
    def lca(self,u,v):#u,v 0-indexedでu,vのlcaを返す
        while True:
            if self.order[u]>self.order[v]:
                u,v=v,u
            if self.head[u]==self.head[v]:
                return u
            v = self.par[self.head[v]]
    
N = int(input())
edge = [[] for i in range(N)]
for i in range(N-1):
    u,v = map(int, input().split())
    u-=1;v-=1
    edge[u].append(v)
    edge[v].append(u)
HLD = HeavyLightDecomposition(N,edge)

Q = int(input())
visited = [-1]*N
dp = [0]*N
ans = 0
for i in range(Q):
    a,b = map(int, input().split())
    a-=1;b-=1
    dp[a] += 1
    dp[b] += 1
    tmp = HLD.lca(a,b)
    dp[tmp]-=1
    if HLD.par[tmp] != -1:
        dp[HLD.par[tmp]]-=1
#print(dp)
visited[0] = 1
ans = 0
def dfs(now):
    global ans
    #print(now)
    for _next in edge[now]:
        if visited[_next] == -1:
            visited[_next] = 1
            dfs(_next)
            dp[now] += dp[_next]
    ans += (dp[now]+1) * dp[now] //2
dfs(0)
print(ans)
0