結果

問題 No.1227 I hate ThREE
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2021-03-17 15:13:14
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 448 ms / 2,000 ms
コード長 2,670 bytes
コンパイル時間 666 ms
コンパイル使用メモリ 82,768 KB
実行使用メモリ 123,552 KB
最終ジャッジ日時 2024-11-14 18:25:39
合計ジャッジ時間 10,312 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 37 ms
53,364 KB
testcase_01 AC 38 ms
53,724 KB
testcase_02 AC 37 ms
53,304 KB
testcase_03 AC 66 ms
71,832 KB
testcase_04 AC 67 ms
71,420 KB
testcase_05 AC 79 ms
73,252 KB
testcase_06 AC 39 ms
52,880 KB
testcase_07 AC 38 ms
53,264 KB
testcase_08 AC 108 ms
81,452 KB
testcase_09 AC 86 ms
73,872 KB
testcase_10 AC 72 ms
69,992 KB
testcase_11 AC 408 ms
118,832 KB
testcase_12 AC 439 ms
123,540 KB
testcase_13 AC 53 ms
64,132 KB
testcase_14 AC 84 ms
73,512 KB
testcase_15 AC 115 ms
83,272 KB
testcase_16 AC 205 ms
93,536 KB
testcase_17 AC 140 ms
85,736 KB
testcase_18 AC 267 ms
101,520 KB
testcase_19 AC 218 ms
95,348 KB
testcase_20 AC 284 ms
103,836 KB
testcase_21 AC 46 ms
61,620 KB
testcase_22 AC 225 ms
95,952 KB
testcase_23 AC 433 ms
121,540 KB
testcase_24 AC 446 ms
123,368 KB
testcase_25 AC 448 ms
123,552 KB
testcase_26 AC 424 ms
119,060 KB
testcase_27 AC 432 ms
122,152 KB
testcase_28 AC 442 ms
123,384 KB
testcase_29 AC 445 ms
123,132 KB
testcase_30 AC 419 ms
120,164 KB
testcase_31 AC 416 ms
120,268 KB
testcase_32 AC 437 ms
122,796 KB
testcase_33 AC 412 ms
120,056 KB
testcase_34 AC 428 ms
121,608 KB
testcase_35 AC 410 ms
119,084 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