## DMOPC '17 Contest 3 P6 - Mimi and Scarf

View as PDF

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

Authors:
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 patches of wool knitted together. Unfortunately, something went very wrong and the scarf ended up as a tree instead of a simple path. The patch is coloured with colour , 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 of length larger or equal to a given value where and where is the node in subpath from one of '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.

#### Input Specification

The first line of input will contain space-separated integers: and .
The next line of input will contain space-separated integers: , indicating that the colour of patch is .
The next lines of input will each contain integers, and , indicating that there is an edge between and ().

#### 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

4

#### Explanation for Sample 1

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

#### 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

6