結果

問題 No.399 動的な領主
ユーザー N-noa21N-noa21
提出日時 2024-08-15 14:00:00
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 3,826 bytes
コンパイル時間 245 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 98,304 KB
最終ジャッジ日時 2024-08-15 14:00:12
合計ジャッジ時間 9,565 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 32 ms
52,736 KB
testcase_01 AC 34 ms
52,588 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 AC 280 ms
98,304 KB
testcase_15 AC 305 ms
98,176 KB
testcase_16 AC 390 ms
96,956 KB
testcase_17 WA -
testcase_18 WA -
権限があれば一括ダウンロードができます

ソースコード

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))
                paths.append((self.par[u]+1,self.par[u]+2))
                return paths
    
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)
#print(HLD.order)
"""
#セグ木に乗せる例(距離)

#セグ木の初期化
if HLD.par[a] == b:#aが子なら整理した順序のorder上のaにaとbの辺の重さwを持たせる
    l[HLD.order[a]] = w
else:#それの逆
    l[HLD.order[b]] = w

seg = Segtree(l,0,f)

#aが親で、a-b間の辺の重さをxに変更
if HLD.par[a] == b:#aが子なら整理した順序のorder上のaにaとbの辺の重さxを持たせる
    l[HLD.order[a]] = x
else:#それの逆
    l[HLD.order[b]] = x


#u~vの間の距離の和
for e_u,e_v in HLD.decomposition(u,v):#分解した区間ごとに足す
    ans += seg.query(e_u,e_v)
"""

data0 = [0]*(N+1)
data1 = [0]*(N+1)
# 区間[l, r)に x を加算
def _add(data, k, x):
    while k <= N:
        data[k] += x
        k += k & -k
def add(l, r, x):
    _add(data0, l, -x*(l-1))
    _add(data0, r, x*(r-1))
    _add(data1, l, x)
    _add(data1, r, -x)

# 区間[l, r)の和を求める
def _get(data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s
def query(l, r):
    return _get(data1, r-1) * (r-1) + _get(data0, r-1) - _get(data1, l-1) * (l-1) - _get(data0, l-1)

Q = int(input())
ans = 0
for i in range(Q):
    a,b = map(int, input().split())
    a-=1;b-=1
    for j,k in HLD.decomposition(a,b):
        add(j+1,k+1,1)
    #print(HLD.decomposition(a,b))
for i in range(1,N+1):
    tmp = query(i,i+1)
    ans += (1+tmp) * tmp //2
print(ans)
0