Transpordikulud

면접 대비

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

요약

트리와 K개의 표시된 도시가 주어질 때, 표시된 도시들로부터의 거리 제곱 합이 최소가 되는 한 도시를 고르는 문제입니다.

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

문제

Bitlandis on $N$ linna, mis on tähistatud arvudega $1$ kuni $N$ . Linnad on omavahel ühendatud $N - 1$ kahesuunalise teega. Iga tee pikkus on üks ühik ja tekkinud teedevõrk on sidus (igast linnast saab liikuda igasse teise linna).

Bitlandi $K$ suurimat linna soovivad korraldada oma õpilastele programmeerimisvõistluse. Nad tahavad korraldada võistluse linnas, mis minimeerib õpilaste transpordikulud. Võistlus võib aset leida ükskõik missuguses Bitlandi linnas.

Õpilaste transportimine linnast $u$ linna $v$ maksab $x^2$ eurot, kus $x$ on $u$ ja $v$ vaheline kaugus. Leia minimaalne võimalik transpordikulu.

입력

Tekstifaili esimesel real on kaks täisarvu, linnade arv $N$ ( $1 \le N \le 5 \cdot 10^5$ ) ja võistlusel osalevate linnade arv $K$ ( $1 \le K \le N$ ). Järgmisel $N - 1$ real on igaühel kaks täisarvu $u$ ja $v$ , mis näitavad, et linnade $u$ ja $v$ vahel on tee. Viimasel real on $K$ suurima linna tähised.

출력

Tekstifaili väljastada minimaalne transpordikulude summa eurodes.

예제2

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

예제 2

입력

예상 출력