PhonePe Online Assissment | Off-Campus | 2027 Grad | Camera On | Codeforces Style Problem Statement

Could not take image as the camera was on. Here is the question what i remember -

Luna and the Colorful Socks

Luna is going on a trip for M days. She owns N socks, numbered from 1 to N. Each sock has one of K possible colors.

Before Luna leaves, her mother gives her instructions for each of the M days. On day i, Luna must wear sock Li on her left foot and sock Ri on her right foot.

However, Luna notices that on some days, the two socks specified by her mother may have different colors.

Luna wants to repaint some of her socks before leaving so that, for every day, the two socks she is instructed to wear have the same color.

There are K available colors. Repainting any sock to color u costs cost[u]. A sock that already has color u does not need to be repainted and therefore incurs no cost.

Each sock can be repainted at most once, and all repainting must be completed before the trip begins.

Find the minimum total cost required so that Luna can follow her mother's instructions on every one of the M days.

Input Format The first line contains three integers:

N M K

where:

• N is the number of socks.
• M is the number of days.
• K is the number of available colors. The second line contains N integers:

C1 C2 ... CN

where Ci denotes the initial color of sock i.

The third line contains K integers:

cost[1] cost[2] ... cost[K]

where cost[u] is the cost of repainting one sock to color u.

Each of the next M lines contains two integers:

Li Ri

meaning that on day i, Luna must wear socks Li and Ri. These two socks must have the same color after all repainting is completed.

Constraints

• 2 <= N <= 200,000
• 0 <= M <= 200,000
• 1 <= K <= 50
• 1 <= Ci <= K
• 1 <= cost[u] <= 10^9
• 1 <= Li, Ri <= N
• Li != Ri

Output Format Print a single integer representing the minimum total repainting cost required to ensure that, for every day, the two socks specified by Luna's mother have the same color.