結果

問題 No.1227 I hate ThREE
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-03-17 15:13:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 429 ms / 2,000 ms
コード長 2,670 bytes
コンパイル時間 2,390 ms
コンパイル使用メモリ 82,208 KB
実行使用メモリ 123,536 KB
最終ジャッジ日時 2024-04-27 01:57:28
合計ジャッジ時間 11,399 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 34 ms
54,112 KB
testcase_01 AC 33 ms
53,196 KB
testcase_02 AC 32 ms
52,832 KB
testcase_03 AC 57 ms
71,316 KB
testcase_04 AC 59 ms
70,532 KB
testcase_05 AC 71 ms
73,400 KB
testcase_06 AC 33 ms
53,136 KB
testcase_07 AC 32 ms
53,632 KB
testcase_08 AC 91 ms
81,192 KB
testcase_09 AC 77 ms
73,272 KB
testcase_10 AC 63 ms
69,148 KB
testcase_11 AC 360 ms
118,892 KB
testcase_12 AC 381 ms
123,528 KB
testcase_13 AC 49 ms
63,468 KB
testcase_14 AC 73 ms
72,604 KB
testcase_15 AC 99 ms
83,044 KB
testcase_16 AC 176 ms
93,404 KB
testcase_17 AC 121 ms
85,688 KB
testcase_18 AC 234 ms
101,004 KB
testcase_19 AC 186 ms
95,320 KB
testcase_20 AC 246 ms
103,340 KB
testcase_21 AC 40 ms
62,028 KB
testcase_22 AC 198 ms
95,928 KB
testcase_23 AC 379 ms
121,424 KB
testcase_24 AC 388 ms
123,536 KB
testcase_25 AC 429 ms
123,268 KB
testcase_26 AC 360 ms
118,928 KB
testcase_27 AC 386 ms
122,172 KB
testcase_28 AC 397 ms
122,992 KB
testcase_29 AC 391 ms
122,840 KB
testcase_30 AC 376 ms
119,916 KB
testcase_31 AC 369 ms
119,956 KB
testcase_32 AC 404 ms
122,520 KB
testcase_33 AC 371 ms
119,876 KB
testcase_34 AC 373 ms
121,672 KB
testcase_35 AC 371 ms
119,284 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main0(n,c,ab):
  ki=[[] for _ in range(n)]
  for a,b in ab:
    a,b=a-1,b-1
    ki[a].append(b)
    ki[b].append(a)
  mod=10**9+7
  tree_order=[]
  todo=[[0,-1]]
  parent=[-1]*n
  while todo:
    v,p=todo.pop()
    parent[v]=p
    tree_order.append(v)
    for nv in ki[v]:
      if nv==p:continue
      todo.append([nv,v])
  tree_order.reverse()
  # c<kx10^3ぐらいのときの解法をまず考える。
  # 1~c -> 0~c-1とする
  dp=[[1]*c for _ in range(n)]
  # dp[v][i]頂点vの部分木を考え、頂点vに値iを入れる場合数
  for v in tree_order:
    # 親へ遷移
    p=parent[v]
    if p<0:continue
    ary=[0]*c
    for i in range(c):
      if i-3>=0:
        ary[i-3]+=dp[v][i]
        ary[i-3]%=mod
      if i+3<c:
        ary[i+3]+=dp[v][i]
        ary[i+3]%=mod
    for i in range(c):
      dp[p][i]*=ary[i]
      dp[p][i]%=mod
  ret=0
  for x in dp[0]:
    ret+=x
    ret%=mod
  return ret

def main1(n,c,ab):
  if c<=2*n:return main0(n,c,ab)
  ki=[[] for _ in range(n)]
  for a,b in ab:
    a,b=a-1,b-1
    ki[a].append(b)
    ki[b].append(a)
  mod=10**9+7
  dist=[0]*n
  max_dist=0
  tree_order=[]
  todo=[[0,-1]]
  parent=[-1]*n
  while todo:
    v,p=todo.pop()
    parent[v]=p
    tree_order.append(v)
    for nv in ki[v]:
      if nv==p:continue
      todo.append([nv,v])
      dist[nv]=dist[v]+1
      max_dist=max(max_dist,dist[nv])

  tree_order.reverse()

  # 1~c -> 0~c-1 -> 0~6*n-1とする
  dp=[[1]*(6*n) for _ in range(n)]
  # dp[v][i]:頂点vの部分木についての解。頂点vに値iを入れる場合数。
  for v in tree_order:
    # 親へ遷移
    p=parent[v]
    if p<0:continue
    ary=[0]*(6*n)
    for i in range(6*n):
      if i-3>=0:
        ary[i-3]+=dp[v][i]
        ary[i-3]%=mod
      if i+3<6*n:
        ary[i+3]+=dp[v][i]
        ary[i+3]%=mod
    for i in range(6*n):
      dp[p][i]*=ary[i]
      dp[p][i]%=mod
  ret=0
  for i in range(3*max_dist):
    x=dp[0][i]
    ret+=x
    ret%=mod
    x=dp[0][-1-i]
    ret+=x
    ret%=mod
  ret+=dp[0][3*max_dist]*(c-3*(max_dist)*2)
  ret%=mod
  return ret

import sys
input=sys.stdin.readline
if __name__=='__main__':
  n,c=map(int,input().split())
  ab=[list(map(int,input().split())) for _ in range(n-1)]
  print(main1(n,c,ab))


if __name__=='__main__1':
  from random import randint,shuffle
  for _ in range(100):
    n=randint(2,50)
    c=randint(4,200)
    ab=[]
    su=[1]
    mi=list(range(2,n+1))
    shuffle(mi)
    while mi:
      a=mi.pop()
      b=su[randint(0,len(su))-1]
      ab.append([a,b])
    ret0=main0(n,c,ab)
    ret1=main1(n,c,ab)
    if ret0!=ret1:
      print(n,c)
      for x in ab:print(*x)
      print((ret0,ret1))
      break
0