DMOPC '17 Contest 3 P6 - Mimi and Scarf

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 1.8s
Memory limit: 256M

Authors:
Problem types

Mimi knitted a scarf for herself. This scarf can be seen as N patches of wool knitted together. Unfortunately, something went very wrong and the scarf ended up as a tree instead of a simple path. The ith patch is coloured with colour ci, where the colours are numbered. Mimi doesn't want to have to knit another scarf, so she plans on choosing a path in this tree. Particularly, she wants the longest possible scarf.

Additionally, Mimi has poor taste: she abhors stripes and does not want anything resembling a striped pattern in her scarf. As such, the path which she selects cannot contain any subpath P of length larger or equal to a given value K where cP1=cP3=cP5= and cP2=cP4=cP6= where Pi is the ith node in subpath P from one of P's endpoints. Note that in this problem, the length of a subpath/path is the number of nodes it contains.

Find the length of the longest possible scarf Mimi can get given this constraint.

Constraints

For all subtasks:

1ciN

Subtask 1 [15%]

2N1000
2KN

Subtask 2 [15%]

2N200000
K=N

Subtask 3 [70%]

2N200000
2KN

Input Specification

The first line of input will contain 2 space-separated integers: N and K.
The next line of input will contain N space-separated integers: c1,c2,,cN, indicating that the colour of patch i is ci.
The next N1 lines of input will each contain 2 integers, a and b, indicating that there is an edge between a and b (1a,bN).

Output Specification

A single integer, the length of the longest possible path which satisfies the constraint. In this problem, the length of a path is the number of nodes it contains.

Sample Input 1

Copy
7 3
1 1 1 2 2 3 3
1 2
2 3
2 4
2 5
6 3
7 1

Sample Output 1

Copy
4

Explanation for Sample 1

The best scarf Mimi can get is the one with patches 7,1,2,5 (there are three other valid paths of the same length other than this path). Note that even though the path from patch 6 to patch 7 has a longer length, it is invalid since it contains the subpath from 1 to 3.

Sample Input 2

Copy
12 4
1 1 1 1 2 2 3 1 3 3 1 2
1 5
5 2
5 3
6 1
6 4
4 10
10 11
11 12
4 7
9 8
7 8

Sample Output 2

Copy
6

Comments

There are no comments at the moment.