解説を参考にFHC Round 2の問題Dを解いてみたんだけど98分（秒じゃない！）かかる上に4つのケースでWA

costly_labels.diff

--- costly_labels.eryk.out	2016-01-26 15:41:09.000000000 +0900
+++ costly_labels.out	2016-01-26 15:31:07.000000000 +0900
@@ -4,10 +4,10 @@
 Case #4: 37158990
 Case #5: 33205878
 Case #6: 35572006
-Case #7: 32836925
+Case #7: 33164452
 Case #8: 14232217
 Case #9: 15
-Case #10: 32539192
+Case #10: 32599945
 Case #11: 15
 Case #12: 37272539
 Case #13: 111
@@ -15,7 +15,7 @@
 Case #15: 15178591
 Case #16: 35513724
 Case #17: 24805514
-Case #18: 18951797
+Case #18: 18973901
 Case #19: 47699753
 Case #20: 28885391
 Case #21: 48321857
@@ -26,5 +26,5 @@
 Case #26: 22610284
 Case #27: 23110537
 Case #28: 1
-Case #29: 14058762
+Case #29: 14498040
 Case #30: 11621588

costly_labels.py

#!/usr/bin/env python
# -*- encoding: utf-8 -*-
from collections import defaultdict
from munkres import Munkres
from toposort import toposort, toposort_flatten

_munkres = Munkres()


def read_ints():
  return map(int, raw_input().split(' '))

def minarg(ar):
  xmin = ar[0]
  at = 0
  for i, x in enumerate(ar):
    if x < xmin:
      xmin = x
      at = i
  return at, xmin


def solve():
  N, K, P = read_ints()
  C = [read_ints() for n in range(N)]
  AB = [read_ints() for n in range(N-1)]

  children = defaultdict(set)
  for Ai,Bi in AB:
    Ai -= 1
    Bi -= 1
    children[Ai].add(Bi)
    children[Bi].add(Ai)

  if children:
   visited = set()
    q = [0]
    while q:
      node = q.pop()
      visited.add(node)
      children[node] = set([child for child in children[node] if child not in visited])
      q += list(children[node])

   deps = toposort_flatten(children)
  else:
    deps = [0]


#  print N,K,P
#  print C
#  print AB
#  print dict(children)

  INFTY = 9999999  # この値は使われない

  DP = [[[INFTY for c in range(K)] for p in range(K)] for i in range(N)]
  for p in range(K):
    if p == 0: continue
    for c in range(K): DP[0][p][c] = None

  for node in deps:
    _children = list(children[node])
    M = len(_children) + (0 if node==0 else 1)

    if len(_children) == 0:
      for p in range(K):
        DP[node][p] = C[node]
        # print 'DP[%d][%d][] = ' % (node,p), C[node]
      continue

    for p in range(K):
      for myc in range(K):
        cost = C[node][myc]

        # (ペナルティ覚悟で最小値のみより集める)
#        colors = [myc] if node > 0 else []
        colors = [p] if node > 0 else []
        for child in _children:
          choices = DP[child][myc]
          # print '  DP[%d][%d] =' % (child, myc), choices
          # assert choices != [INFTY]*K
          at, xmin = minarg(choices)
          colors.append(at)
          cost += xmin
        if len(set(colors)) < len(colors):
          cost += P # penalty
        # とりま
        DP[node][p][myc] = cost
        # print 'DP[%d][%d][%d] = %d' % (node,p,myc,cost)
        if M > K:
          continue

        # ハンガリアン頑張る
        assert M <= K

        def drop(lis, ix):
          return lis[:ix] + lis[ix+1:]
        if node == 0:
          matrix = [DP[child][myc] for child in _children]
        else:
          matrix = [drop(DP[child][myc],p) for child in _children]

        indices = _munkres.compute(matrix)
        cost = 0
        for i, index in indices:
          ix = indices[i]
          cost += matrix[i][index]
        cost += C[node][myc]
        DP[node][p][myc] = cost
        # print 'DP[%d][%d][%d] = %d <munkres>' % (node,p,myc,cost)

  # print DP
  return min(DP[0][0])


def main():
  T = read_ints()[0]
  for t in range(T):
    ans = solve()
    print "Case #%d: %s" % (1+t, ans)


if __name__ == '__main__':
  main()