結果

問題 No.399 動的な領主
ユーザー timitimi
提出日時 2023-05-18 11:37:39
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,168 ms / 2,000 ms
コード長 1,641 bytes
コンパイル時間 210 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 228,116 KB
最終ジャッジ日時 2024-05-09 13:50:06
合計ジャッジ時間 13,991 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 56 ms
52,480 KB
testcase_01 AC 51 ms
52,480 KB
testcase_02 AC 54 ms
53,632 KB
testcase_03 AC 61 ms
53,760 KB
testcase_04 AC 134 ms
76,672 KB
testcase_05 AC 273 ms
82,304 KB
testcase_06 AC 1,121 ms
122,112 KB
testcase_07 AC 1,139 ms
118,204 KB
testcase_08 AC 1,149 ms
117,784 KB
testcase_09 AC 1,167 ms
119,492 KB
testcase_10 AC 167 ms
77,952 KB
testcase_11 AC 258 ms
81,536 KB
testcase_12 AC 1,008 ms
114,816 KB
testcase_13 AC 964 ms
114,816 KB
testcase_14 AC 819 ms
228,116 KB
testcase_15 AC 899 ms
227,988 KB
testcase_16 AC 985 ms
174,720 KB
testcase_17 AC 1,168 ms
119,620 KB
testcase_18 AC 998 ms
116,860 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

N=int(input())
D=[[] for i in range(N)]
G=[[] for i in range(N)]
S=[]
F=[0]*N
for i in range(N-1):
  u,v=map(int, input().split())
  u-=1;v-=1
  D[u].append(v)
  D[v].append(u)
#根が決められておらず、Dでとりあえず双方向を記録し、Gで方向を決めている
DIN=[-1]*N
DOU=[-1]*N
depth=[-1]*N
import sys
sys.setrecursionlimit(10**9)
k=0
P=[-1]*N
def dfs(v,d,pre):
  F[v]=len(S)
  global k
  DIN[v]=k
  k+=1
  depth[v]=d
  S.append(v)
  P[v]=pre
  for u in D[v]:
    if u!=pre:
      G[v].append(u)
      dfs(u,d+1,v)
      S.append(v)
  DOU[v]=k
  k+=1

dfs(0,0,0)
P[0]=-1
DE={}
for i in range(N):
  if depth[i] not in DE:
    DE[depth[i]]=[i]
  else:
    DE[depth[i]].append(i)
#LCA
M=2*N
INF=(N,None)
M0=2**(M-1).bit_length()
data=[INF]*(2*M0)
for i, v in enumerate(S):
  data[M0-1+i]=(depth[v],i)
for i in range(M0-2, -1, -1):
  data[i]=min(data[2*i+1], data[2*i+2])

def _query(a, b):
    yield INF
    a += M0; b += M0
    while a < b:
        if b & 1:
            b -= 1
            yield data[b-1]
        if a & 1:
            yield data[a-1]
            a += 1
        a >>= 1; b >>= 1

# LCAの計算 (外から呼び出す関数)
def query(u, v):
    fu = F[u]; fv = F[v]
    if fu > fv:
        fu, fv = fv, fu
    return S[min(_query(fu, fv+1))[1]]

E=[0]*N
Q=int(input())
for i in range(Q):
  u,v=map(int, input().split())
  u-=1;v-=1
  E[u]+=1;E[v]+=1
  c=query(u,v)
  cc=P[c]
  E[c]-=1
  if cc!=-1:
    E[cc]-=1

ans=[0]*N
EE=sorted(list(set(depth)))[::-1]
for e in EE:
  for now in DE[e]:
    c=E[now]
    for ch in G[now]:
      c+=ans[ch]
    ans[now]=c
c=0
for i in ans:
  c+=i*(i+1)//2
print(c)
0