Fleksibilan fikus

시간 제한1초메모리 제한1024 MB

요약

남은 트리가 연결되고 노드가 k개 이상이 되도록 일부 노드를 제거할 때, 남은 노드 값들의 비트 AND를 최대로 만드는 값을 구합니다.

난이도: 보통10점 중 7점
유형: 트리, DFS, 그리디, 비트 연산
정답자: 아직 제출이 없습니다

문제

Gospodin Malnar promatrao je svoj fikus i zaključio da nije dovoljno fleksibilan. Njegov fikus možemo zamisliti kao stablo s $n$ čvorova gdje svaki čvor ima svoju fleksibilnost $F\_i$ . Gospodin Malnar odrezat će neki skup čvorova tako da stablo ostane povezano $i$ da ostane barem $k$ čvorova. Tada se fleksibilnost stabla definira kao bitovni and $F\_i$ svih čvorova unutar stabla. Sada ga zanima koja je najveća fleksibilnost koju može postići.

입력

U prvom su retku brojevi $n$ ( $1 ≤ n ≤ 10^5$ ) i $k$ ( $1 ≤ k ≤ n$ ) tj. broj čvorova u stablu i broj $k$ iz teksta zadatka.

U drugom retku nalazi se $n$ brojeva od kojih $i$ -ti označava $F\_i$ ( $0 ≤ F\_i < 2^{30}$ ).

U sljedećih $n - 1$ redaka nalaze se brojevi $u\_i$ te $v\_i$ ( $1 ≤ u\_i , v\_i ≤ n$ , $u\_i \ne v\_i$ ) koji označavaju da su čvorovi $u\_i$ te $v\_i$ spojeni bridom.

출력

U jedinom retku potrebno je ispisati maksimalnu fleksibilnost koju Gospodin Malnar može postići.

힌트

Pojašnjenje prvog probnog primjera: Najveća se fleksibilnost postiže micanjem čvora 5.

예제2

예제 1
입력
```
5 4
6 2 7 10 5
1 2
2 3
2 4
1 5
```
예상 출력
```
2
```
예제 2
입력
```
4 2
3 1 3 2
1 2
2 3
3 4
```
예상 출력
```
2
```