まず、いくらかの観察により小問題は二部マッチングとして解釈できることがわかります。二部マッチングとして定式化し直したものが以下となります：

木 \(T, U\) を頂点 \(k\) を根とする根付き木とみなして考える。
木 \(T\) における頂点 \(k\) の子を \(b_1, b_2, \dots, b_n\) とする。
木 \(U\) における頂点 \(k\) の子を \(c_1, c_2, \dots, c_m\) とする。
この時、次の \(n+m\) 頂点 \(N-1\) 辺の二部グラフを考える。

• 左側の部集合に含まれる頂点は頂点 \(1, 2, \dots, n\) と番号がついている。
• 右側の部集合に含まれる頂点は頂点 \(1, 2, \dots, m\) と番号がついている。
• \(1 \leq i \leq N\) かつ \(i \neq k\) を満たす整数 \(i\) について、木 \(T\) において頂点 \(i\) が \(b_j\) の部分木に属して、木 \(U\) において頂点 \(i\) が \(c_k\) の部分木に属するとする。この時、左側の頂点 \(j\) と右側の頂点 \(k\) の間に重み \(A_i\) の辺が張られている。

上記の二部グラフにおけるサイズ \(4\) のマッチングの重み和の最小値が小問題の答えとなる。ただしサイズ \(4\) のマッチングが存在しない場合は答えは \(-1\) となる。

全ての小問題に対する \(n+m\) の総和は \(2N\) で抑えられます。よって、小問題あたり \(\tilde{O}(n+m)\) で解くことが出来ればよいです。

小問題で登場する二部グラフをそのまま構成すると \(\mathrm{O}(N)\) 本の辺が発生して計算量が破綻するので辺を削減することを考えます。具体的には以下の手順で辺を削除すると辺が \(\mathrm{O}(n)\) 本になります。(正当性の証明の詳細は割愛しますが、「削除した辺を用いるマッチングは、その辺を削除しなかった辺に上手く置き換えても悪化しない」という方針で証明できます。)

• まず、両端点が一致する辺たちについては最も重みの小さい辺のみを残してそれ以外の辺を削除する。
• その後、各左側頂点 \(i\) について、\(i\) から伸びる辺のうち重みの小さい方から \(4\) 本までを残し、それ以外は削除する。

実際に辺数を \(\mathrm{O}(n)\) 本に減らすことが出来れば、小問題は最小費用流を解くアルゴリズムを用いて \(\mathrm{O}((n+m) \log (n+m))\) で解くことが出来ます。

以上の議論により、今回の問題は \(k=1,2,\dots,N\) に対して次の処理を行う問題に帰着されました。

木 \(T, U\) を頂点 \(k\) を根とする根付き木とみなして考える。
木 \(T\) における頂点 \(k\) の子を \(b_1, b_2, \dots, b_n\) とする。
木 \(U\) における頂点 \(k\) の子を \(c_1, c_2, \dots, c_m\) とする。
\(i = 1, 2, \dots, n\) に対して、\(T\) における \(b_i\) の部分木に含まれる頂点 \(v\) のうち \(A_v\) が小さいものを \(4\) 個まで取り出せ。ただし、頂点 \(v_1, v_2\) が \(U\) においてどちらも \(c_j\) の部分木に所属している場合、これらを同時に取り出すことはできない。

上記の処理をデータ構造に載せやすいように少し見方を変えてみます。

木 \(T, U\) を頂点 \(k\) を根とする根付き木とみなして考える。
木 \(T\) における頂点 \(k\) の子を \(b_1, b_2, \dots, b_n\) とする。
木 \(U\) における頂点 \(k\) の子を \(c_1, c_2, \dots, c_m\) とする。
まず、\(v=1,2,\dots,N\) について、木 \(U\) において頂点 \(v\) が \(c_j\) の部分木に所属するとした時、木 \(T\) の頂点 \(v\) を色 \(j\) に塗る。
そして、\(i = 1, 2, \dots, n\) に対して、\(T\) における \(b_i\) の部分木に含まれる頂点 \(v\) のうち \(A_v\) が小さいものを \(4\) 個まで取り出せ。ただし同じ色の頂点は \(1\) 回までしか選べない。

このように言い換えると、各 \(i\) におけるクエリがオイラーツアー + セグメント木で処理できる形であることがわかります。すなわち、「色の異なる頂点を \(4\) 個まで持ったデータ」同士のマージは高速に行えるため、セグメント木に載せられます。

問題は各頂点に色を塗る操作で、現状では \(\mathrm{O}(N^2)\) 回色を塗りかえることになるので、この部分をより少ない回数の色の塗り替えで処理できれば今回の問題を解くことが出来ます。言い換えると、以下の問題が解ければよいです。

はじめ全ての頂点は色 \(0\) で塗られています。
\(\mathrm{o}(N^2)\) 回の色を塗り替える操作を用いて \(k=1,2,\dots,N\) について以下の状態を出現させてください。(出現させる順番は自由)

• 木 \(U\) を頂点 \(k\) を根とする根付き木とみなして考える。
  木 \(U\) における頂点 \(k\) の子を \(c_1, c_2, \dots, c_m\) とする。
  各 \(c_j\) の部分木について、部分木内の頂点に塗られている色が一致していて、かつ異なる部分木に含まれる頂点同士の色が異なっている。

この問題は重軽分解の構造を用いることで \(\mathrm{O}(N \log N)\) 回の色の塗り替えで済ませることが出来ます。(DSU on Tree と呼ばれるアルゴリズムの亜種とみなすこともできます。)

木 \(U\) を頂点 \(1\) とする根付き木として考えます。頂点 \(k\) の子を \(d_1, d_2, \dots, d_l\) とします。そして \(d_1\) を heavy child とします。出現させたいのは次の条件を満たす状態です：

• \(d_i\) の部分木には色 \(i\) が塗られている
• それ以外の頂点、すなわち \(k\) の親に向かう辺を経由して到達できる頂点には色 \(0\) が塗られている

これは以下の手順で DFS を行うことで実現できます。

def dfs(k, keep):
  for c in (light child of k):
    dfs(c, 0)
  if k is not leaf:
    dfs(d_1, 1)  # heavy child
  for i = 2 to (the number of children of k):
    paint descendants of d_i with color i
  process the k-th query
  if keep == 0:
    paint descendants of k with color 0
  else:
    paint vertex k with 1
    for c in (light child of k):
      paint descendants of c with color 1

各頂点 \(v\) はその祖先方向に存在する light edge の本数のオーダーだけ色を塗り替えられるので、全体の色を塗り替える回数は \(\mathrm{O}(N \log N)\) 回に抑えられます。よって、色を塗り替えるごとにセグメント木のデータを更新することも踏まえると、この部分の計算量は \(\mathrm{O}(N \log^2 N)\) となります。

以上のアルゴリズムを全て適切に実装することで今回の問題を解くことが出来ました。計算量は \(\mathrm{O}(N \log^2 N)\) でこれは十分高速です。