結果

問題 No.399 動的な領主
ユーザー N-noa21N-noa21
提出日時 2024-08-15 16:47:46
言語 PyPy3
(7.3.15)
結果
RE  
実行時間 -
コード長 3,251 bytes
コンパイル時間 209 ms
コンパイル使用メモリ 82,112 KB
実行使用メモリ 98,688 KB
最終ジャッジ日時 2024-08-15 16:47:54
合計ジャッジ時間 7,793 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
53,144 KB
testcase_01 AC 39 ms
53,256 KB
testcase_02 AC 41 ms
54,484 KB
testcase_03 AC 41 ms
54,940 KB
testcase_04 AC 96 ms
76,384 KB
testcase_05 AC 178 ms
79,628 KB
testcase_06 AC 561 ms
96,912 KB
testcase_07 AC 525 ms
95,968 KB
testcase_08 AC 523 ms
95,704 KB
testcase_09 AC 512 ms
95,756 KB
testcase_10 AC 107 ms
76,772 KB
testcase_11 AC 146 ms
79,084 KB
testcase_12 AC 428 ms
96,420 KB
testcase_13 AC 443 ms
96,620 KB
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 AC 542 ms
96,756 KB
testcase_18 AC 500 ms
95,912 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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