結果

問題 No.399 動的な領主
ユーザー N-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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

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)
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0