結果
問題 | No.1227 I hate ThREE |
ユーザー |
|
提出日時 | 2020-09-11 22:57:33 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 162 ms / 2,000 ms |
コード長 | 2,846 bytes |
コンパイル時間 | 346 ms |
コンパイル使用メモリ | 82,080 KB |
実行使用メモリ | 102,948 KB |
最終ジャッジ日時 | 2025-01-02 05:44:33 |
合計ジャッジ時間 | 4,216 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
import sysinput = sys.stdin.readlinesys.setrecursionlimit(2*10**5)mod = 10**9+7N,C = map(int,input().split())edge = [[] for i in range(N)]for i in range(N-1):a,b = map(int,input().split())edge[a-1].append(b-1)edge[b-1].append(a-1)depth = [-1 for i in range(N)]parent = [-1 for i in range(N)]size = [1 for i in range(N)]depth[0] = 0def dfs(v,pv):for nv in edge[v]:if nv!=pv:parent[nv] = vdepth[nv] = depth[v] + 1dfs(nv,v)size[v] += size[nv]dfs(0,-1)D = max(depth)def solve(M):if M<=2*D+1:dp = [[1 for i in range(M)] for j in range(N)]def dp_dfs(v,pv):for nv in edge[v]:if nv!=pv:dp_dfs(nv,v)for i in range(M):tmp = 0if i!=0:tmp += dp[nv][i-1]if i!=M-1:tmp += dp[nv][i+1]tmp %= moddp[v][i] *= tmpdp[v][i] %= moddp_dfs(0,-1)res = 0for i in range(M):res += dp[0][i]res %= modreturn reselse:dp_low = [[1 for i in range(D+1)] for j in range(N)]dp_high = [[1 for i in range(D+1)] for j in range(N)]def dp_dfs(v,pv):for nv in edge[v]:if nv!=pv:dp_dfs(nv,v)for i in range(D+1):tmp = 0if i!=0:tmp += dp_low[nv][i-1]if i!=D:tmp += dp_low[nv][i+1]else:tmp += pow(2,size[nv]-1,mod)tmp %= moddp_low[v][i] *= tmpdp_low[v][i] %= modtmp = 0if i!=0:tmp += dp_high[nv][i-1]if i!=D:tmp += dp_high[nv][i+1]else:tmp += pow(2,size[nv]-1,mod)tmp %= moddp_high[v][i] *= tmpdp_high[v][i] %= moddp_dfs(0,-1)res = 0for i in range(D+1):res += dp_low[0][i]res %= modres += dp_high[0][i]res %= modtmp = pow(2,N-1,mod) * (M-2*D-2) %modres += tmpres %= modreturn resans = 0c = C//3if C%3==1:ans += solve(c+1) + 2*solve(c)ans %= modelif C%3==2:ans += 2*solve(c+1) + solve(c)ans %= modelse:ans = 3*solve(c)ans %= modprint(ans)