Closer

Observation 1: the pairs are a red herring

The statement talks about pairs of equal badges. Cute. But the score after the reshuffle is simply:

$$\sum_{(u,v)\in E} [\text{final badge on }u = \text{final badge on }v] \cdot w_{\text{that badge}}.$$

So instead of tracking each deal separately, track what badge ends up on each endpoint of each edge.

Because chosen edges form a matching, every vertex either:

• stays put, or
• swaps with exactly one neighbor.

That means every final badge moves by at most one edge. This is the key thing that makes the DP small instead of disgusting.

---

Observation 2: root the tree and look only at the root of each subtree

Root the tree arbitrarily, say at vertex $1$.

Consider a node $v$.

If the edge to its parent is not selected, then the final badge on $v$ can only be:

• its own badge $a_v$, or
• the badge of one of its children $a_c$ (if $v$ swaps with child $c$).

So the set of possible final badges on $v$ is just

$$\{a_v\} \cup \{a_c : c \text{ is a child of } v\}.$$

That is only $1 + \deg(v)$ possibilities.

If the edge $(p(v),v)$ is selected, then $v$ swaps with its parent, so the final badge on $v$ is forced to be

$$a_{p(v)}.$$

That’s it. No wild badge teleports, no cursed global dependencies. The tree is behaving for once.

---

DP meaning

For each node $v$, we maintain two kinds of information.

1. States when $v$ is not matched to its parent

For every label $L$ that can end up on $v$, define:

$$S_v(L) = \text{maximum score inside subtree } T_v \text{ when the final badge on } v \text{ is } L,$$

and the edge to the parent is not selected.

Also define

$$B_v = \max_L S_v(L).$$

This is “best possible if parent doesn’t care what badge sits on $v$”.

2. State when $v$ is matched to its parent

Define

$$U_v = \text{maximum score inside } T_v \text{ when } (p(v),v) \text{ is selected}.$$

Then $v$ cannot swap with any child, and the final badge on $v$ is fixed to $a_{p(v)}$.

---

How a child contributes when the edge to it is not selected

Fix a node $v$, a child $c$, and suppose the final badge on $v$ is some label $L$.

If edge $(v,c)$ is not selected, then the child subtree can be arranged in any state with parent-edge unused. Two options:

1. Don’t make $(v,c)$ equal. Then contribution is just $B_c$.
2. Force final badge on $c$ to also be $L$, so edge $(v,c)$ becomes equal and contributes $w_L$. Then contribution is $S_c(L)+w_L$.

So the best contribution of child $c$ is

$$g_c(L)=\max\big(B_c,\ S_c(L)+w_L\big).$$

Now sum over children:

$$F_v(L)=\sum_{c\in child(v)} g_c(L).$$

Interpretation: if the final badge on $v$ is fixed to $L$, and $v$ is not matched to any child, this is the best total contribution of all child sides.

---

The two real transitions

Case 1: $v$ keeps its own badge

Then the final badge on $v$ is $a_v$, and $v$ doesn’t swap with any child.

So:

$$S_v(a_v) \text{ gets candidate } F_v(a_v).$$

Let’s call this value

$$dp_v^{self}=F_v(a_v).$$

Case 2: $v$ swaps with one child $c$

Then:

• edge $(v,c)$ is selected,
• final badge on $v$ becomes $a_c$,
• child $c$ is in the “matched to parent” mode, contributing $U_c$,
• edge $(v,c)$ itself contributes $w_{a_v}$ iff $a_v=a_c$.

For all other children $d\ne c$, we still use the “edge not selected” contribution with label $a_c$ on $v$.

So:

$$S_v(a_c) \text{ gets candidate } U_c + [a_v=a_c]w_{a_v} + F_v(a_c)-g_c(a_c).$$

That subtraction removes child $c$’s old “not selected” contribution, because now edge $(v,c)$ is selected instead.

---

Computing $U_v$

If $v$ is matched to its parent, then the final badge on $v$ is forced to be $a_{p(v)}$, and $v$ cannot match any child.

So simply:

$$U_v = F_v(a_{p(v)}).$$

Very clean. Suspiciously clean, even. But it’s right.

---

The important optimization: don’t do $O(\deg^2)$ garbage

Naively, to compute $F_v(L)$ for every relevant $L$, you’d scan all children every time. On a star, that’s how you lose 3 seconds and your dignity.

Rewrite:

$$g_c(L)=B_c + \max\big(0, S_c(L)+w_L-B_c\big).$$

Define

$$\Delta_c(L)=\max\big(0, S_c(L)+w_L-B_c\big).$$

Then

$$F_v(L)=\sum_c B_c + \sum_c \Delta_c(L).$$

The first part is a constant for node $v$.

The second part only depends on labels $L$ for which child $c$ actually has a state $S_c(L)$. But what labels can appear on $c$?

Only:

$$a_c \quad \text{or} \quad a_x \text{ for a child } x \text{ of } c.$$

So the number of stored labels for node $c$ is at most $1+\deg(c)$.

Hence the total number of $(node,label)$ states over the whole tree is

$$O\left(\sum_v (1+\deg(v))\right)=O(n).$$

That means we can aggregate all positive gains $\Delta_c(L)$ by label in linear total time.

---

What exactly do we store?

For each node $v$:

• a list of pairs $(L, S_v(L))$ for all reachable labels $L$ on $v$,
• $B_v = \max_L S_v(L)$,
• $U_v$,
• and specifically $S_v(a_v)$, because the parent will query the gain for label $a_v$ a lot.

While processing node $v$ bottom-up:

1. Compute $$base = \sum_{c} B_c.$$
2. For every label appearing in some child state map, accumulate $$\Delta_c(L)=\max(0, S_c(L)+w_L-B_c).$$
3. Then $$F_v(L)=base + \text{accumulatedGain}[L].$$
4. Build candidates for $S_v(a_v)$ and for each child-label state $S_v(a_c)$.
5. Compress equal labels by taking the maximum value.

The answer for the whole test case is simply

$$B_{root}.$$

No parent above the root, no extra nonsense.

---

Correctness sketch

We prove by induction on subtree size.

For a leaf, everything is trivial:

• if parent edge not selected, the only possible final badge is $a_v$, with value $0$,
• if parent edge selected, again value $0$ inside the subtree.

Now assume all children of $v$ are solved correctly.

If the parent edge of $v$ is not selected, then any valid configuration falls into exactly one of these mutually exclusive cases:

• $v$ swaps with no child, so final badge on $v$ is $a_v$;
• $v$ swaps with exactly one child $c$, so final badge on $v$ is $a_c$.

Those are the only possibilities because selected edges form a matching.

For each fixed final label $L$ on $v$, every child $d$ with edge $(v,d)$ not selected contributes independently, and the best value is exactly

$$g_d(L)=\max(B_d, S_d(L)+w_L),$$

by the induction hypothesis.

If one child $c$ is selected, then its contribution must be replaced by the matched-to-parent value $U_c$, plus the selected-edge reward if $a_v=a_c$.

So the formulas for $S_v(L)$ are exact, not heuristic.

If the parent edge of $v$ is selected, then $v$ cannot select a child, and the final badge on $v$ is fixed to $a_{p(v)}$, so

$$U_v = F_v(a_{p(v)}).$$

Thus all transitions are correct. Induction closes, and the root answer is optimal.

---

Complexity

Let $N=2n$ be the number of vertices.

Each node stores states only for labels of itself and its children, so the total number of stored states is

$$O\left(\sum_v (1+\deg(v))\right)=O(N).$$

Each state entry is processed only a constant number of times.

So the total complexity per test case is

$$O(N),$$

and over all test cases:

$$O\left(\sum N\right)=O\left(\sum 2n\right)=O\left(\sum n\right).$$

Memory is also linear:

$$O(N).$$

Which is very nice, because anything slower here would get smacked by the limits.