DMOPC '17 Contest 3 P6 - Mimi and Scarf

View as PDF

Submit solution

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

Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 i^{\text{th}} patch is coloured with colour c_i, 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 c_{P_1}=c_{P_3}=c_{P_5}=\dots and c_{P_2}=c_{P_4}=c_{P_6}=\dots where P_i is the i^{\text{th}} 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.


For all subtasks, 1\le c_i \le N.

Subtask 1 [15%]

2\le N \le 1\,000
2\le K \le N

Subtask 2 [15%]

2\le N \le 200\,000

Subtask 3 [70%]

2\le N \le 200\,000
2\le K \le N

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: c_1, c_2, \dots c_N, indicating that the colour of patch i is c_i.
The next N - 1 lines of input will each contain 2 integers, a and b, indicating that there is an edge between a and b (1\le a, b\le N).

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

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

Sample Output 1


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

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



There are no comments at the moment.