$A$ が順列だったら、過去のABCのE～F問題くらいに出たことがあったかも。
証明は簡単ではないが、解法は直感的に思いつきやすいように思う。
$A$ をソートして、最終的な目標となる数列を $B$ とする。
A 3 1 4 1 2 3 2 3
B 1 1 2 2 3 3 3 4
巡回置換を見つける。
Ai→Bi = Aj→Bj = Ak→Bk→...
~~~~
Bi=Aj であるような j を選ぶ、という意味
と辿っていって、$A_i$ に戻ってきたら1つの巡回置換。
A 3 1 4 1 2 3 2 3
B 1 1 2 2 3 3 3 4
i j k 3→1→2→3 の巡回置換
1つの巡回置換ループは、その長さを $n$ として、$n-1$ 回のスワップでそれぞれを正しい値にできる。
なので、なるべく多くのループを作ることで、$N-(ループ数)$ のスワップで全てを正しい値にできる。
順列の場合は $B_i=A_j$ となる $j$ が毎回1つしかないので、巡回置換の取り方も一意に決まるが、、、
今回は「$B_i=A_j$ となる $j$」が複数候補あって、どれを選ぶかでループが変わってくる。
ただ、項が1,2,3,4の4種類しかないので、ループの長さもたかだか4。
1個あたりが短い方から貪欲に確定させられないか、確かめる。
$(A_i,B_i)$ のペア（4×4で16通り）毎にカウントする。
$A_i=B_i$ の場合、そこは長さ1のループと言え、操作する必要は無い。
$(a,b),(b,a)$ というペアは長さ2のループにできる。
貪欲にマッチングさせていくと、$(a,b)$ か $(b,a)$ のいずれかが0になり、もう片方はいくつか残る可能性がある。
「ペアを全てマッチングさせず、いずれも敢えて少し残しておくことで、総合的には得する」ことはあるか？
ない。
数の整合は取れているので、もし最適なループの分け方に「$(a,b)$ だけを含むループと $(b,a)$ だけを含むループ」があった場合、
組み替えて「$(a,b),(b,a)$ のループと、それ以外」にすることが必ず可能。
a→b→c b→a→d→e
^-----' ^--------'
↓
a↔b b→c→a→d→e
^-----------'
ループ数（操作回数）を悪化させずに長さ2のループを増やすことができるので、長さ2は最大まで作ってよい。
長さ3のループを考える。
残りは長さ4しかないので、ここまで来たら長さ3をたくさん作った方がよいのは明らか。
$(a,b),(b,c),(c,a)$ という3つ組を固定すると、$a→b→c$ の長さ3のループになる。
この時、たとえば $(a,b)$ は、$a→b→d$ のループを作るときにも使われるが、$c$ を含む方に貪欲に使ってよいのか？
貪欲に使った結果 $(a,b)$ が足りなくなり $(b,d),(d,a)$ が余ってしまった場合に、
逆にこちらを優先的に消費して、$(b,c),(c,a)$ の方を余らせた方がよかった、ということはないのか？
ない。
2個ペアを最大まで取った後、各 $(a,b),(b,a)$ の片方は0なので、双方向の辺は残っていない。
その上で、$a→b→c$、$a→b→d$ 両方が残っているのは、下の形しかない。
a ----→ b
↑↖ ／│
│ × │ ※(c,d)に関しては、残っているのが (d,c) の方かもしれないが、
│↙ ＼↓ その場合、c,dを入れ替える
d ←---- c
この中でループは $a→b→c,a→b→d,a→b→c→d$ の3通りしかない。
長さ3の2つで共通するペアは $(a,b)$ のみで、長さ3を最大まで取った結果、$(a,b)$ が残ったならそれは長さ3が取れる上限に違いないし、
$(a,b)$ が無くなったら長さ4も取れないので、（全体では整合が取れているので）長さ3の2つだけで残りを全て消費できるということになる。
よって、取る順番に依らず、長さ3のループは貪欲にとっていい。残ったものが長さ4のループとなる。
Python3
from collections import defaultdict
n = int(input())
aaa = list(map(int, input().split()))
bbb = sorted(aaa)
count = defaultdict(int)
for i in range(n):
a = aaa[i] - 1
b = bbb[i] - 1
if a != b:
count[a, b] += 1
ans = 0
ab = list(count.keys())
for a, b in ab:
ab_cnt = count[a, b]
ba_cnt = count[b, a]
if ab_cnt == 0 or ba_cnt == 0:
continue
d = min(ab_cnt, ba_cnt)
ans += d
count[a, b] -= d
count[b, a] -= d
for a, b in ab:
ab_cnt = count[a, b]
if ab_cnt == 0:
continue
for c in range(4):
if a == c or b == c:
continue
bc_cnt = count[b, c]
ca_cnt = count[c, a]
if bc_cnt == 0 or ca_cnt == 0:
continue
d = min(ab_cnt, bc_cnt, ca_cnt)
ans += d * 2
count[a, b] -= d
count[b, c] -= d
count[c, a] -= d
ans += sum(count.values()) // 4 * 3
print(ans)
木ではなくて数列上で同様のことをする問題は、過去に出題されたことがあった。
（$N$ 個のペア $A_i,B_i$ から1つずつ取って種類数を最大化）
数列での解法は、
「ボールに書かれた整数を頂点と見なして、各 $A_i,B_i$ を結んでいく。
各連結成分について、それが木なら辺数、木で無いなら頂点数が、取り得る種類数の最大値」
というもの。
これは、辺数（uniteされた回数）も保持するUnion-Findで実現できる。
木においても同様のことが言えるが、毎回1から各頂点への最短パスでUnion-Findを構築してたら当然TLEなので、
親とかで構築した結果を使い回す必要がある。
頂点1を根としてDFS（オイラーツアー）しながらUnion-Findを操作していくが、
親→子への移動では、子の $A_i,B_i$ を結ぶ
子から親へ戻る移動では、子で結んでいた $A_i,B_i$ を「外す」
という操作が必要になる。
通常のUnion-Findでは外す操作はできないが、外すのは「履歴において直前で結んだ頂点」なので、
履歴を管理して、1手戻す操作を可能にする「Rollback Union-Find」を使うことで、実現できる。
Python3
class RollbackUnionFind:
def __init__(self, n: int):
self.table = [-1] * n
self.edge_count = [0] * n
self.history = [] # (継続リーダー番号1, 被統合リーダー番号2, 1統合前table値, 2統合前table値, 1統合前edge値, 2統合前edge値)
def root(self, x: int):
tbl = self.table
while tbl[x] >= 0:
x = tbl[x]
return x
def find(self, x: int, y: int):
return self.root(x) == self.root(y)
def unite(self, x: int, y: int):
r1 = self.root(x)
r2 = self.root(y)
if r1 == r2:
self.edge_count[r1] += 1
self.history.append((r1, -1, -1, -1, -1, -1))
return False
d1 = self.table[r1]
d2 = self.table[r2]
e1 = self.edge_count[r1]
e2 = self.edge_count[r2]
if d1 <= d2:
self.table[r2] = r1
self.table[r1] += d2
self.history.append((r1, r2, d1, d2, e1, e2))
self.edge_count[r1] += e2 + 1
else:
self.table[r1] = r2
self.table[r2] += d1
self.history.append((r2, r1, d2, d1, e2, e1))
self.edge_count[r2] += e1 + 1
return True
def undo(self):
if not self.history:
return
r1, r2, d1, d2, e1, e2 = self.history.pop()
if r2 == -1:
self.edge_count[r1] -= 1
return False
self.table[r1] = d1
self.table[r2] = d2
self.edge_count[r1] = e1
self.edge_count[r2] = e2
return True
def get_size(self, x: int):
return -self.table[self.root(x)]
n = int(input())
balls = []
for _ in range(n):
a, b = map(int, input().split())
balls.append((a - 1, b - 1))
links = [[] for _ in range(n)]
for _ in range(n - 1):
u, v = map(int, input().split())
u -= 1
v -= 1
links[u].append(v)
links[v].append(u)
# オイラーツアー
progress = [0] * n
parents_vertex = [-1] * n
depths = [0] * n
euler_tour_vertex = [0]
v = 0
while v != 0 or progress[0] < len(links[0]):
if progress[v] >= len(links[v]):
euler_tour_vertex.append(parents_vertex[v])
v = parents_vertex[v]
continue
u = links[v][progress[v]]
progress[v] += 1
if u == parents_vertex[v]:
continue
euler_tour_vertex.append(u)
depths[u] = depths[v] + 1
parents_vertex[u] = v
v = u
first_appear = [-1] * n
last_appear = [-1] * n
for i, v in enumerate(euler_tour_vertex):
if first_appear[v] == -1:
first_appear[v] = i
last_appear[v] = i
cur_ans = 0
ans = [0] * n
uft = RollbackUnionFind(n)
for i, v in enumerate(euler_tour_vertex):
if first_appear[v] == i:
a, b = balls[v]
r1 = uft.root(a)
r2 = uft.root(b)
cur_ans -= min(-uft.table[r1], uft.edge_count[r1])
if r1 != r2:
cur_ans -= min(-uft.table[r2], uft.edge_count[r2])
uft.unite(a, b)
r = uft.root(a)
cur_ans += min(-uft.table[r], uft.edge_count[r])
ans[v] = cur_ans
if last_appear[v] == i:
a, b = balls[v]
r = uft.root(a)
cur_ans -= min(-uft.table[r], uft.edge_count[r])
uft.undo()
r1 = uft.root(a)
r2 = uft.root(b)
cur_ans += min(-uft.table[r1], uft.edge_count[r1])
if r1 != r2:
cur_ans += min(-uft.table[r2], uft.edge_count[r2])
print(*ans[1:])
