콘텐츠 전송

시간 제한5초메모리 제한256 MB

요약

가중 트리에서 경로 캐싱이 적용되는 m번의 배송마다 아이템과 목적지를 골라 크기 곱하기 이동 거리 합을 최대화합니다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 트리, 그리디
정답자: 아직 제출이 없습니다

문제

노드가 $n$ 개인 컴퓨터 네트워크가 있다. 이 네트워크는 무향 트리이고, $i$ 번째 간선은 $a_i$ 번 노드와 $b_i$ 번 노드를 잇는다. 이 간선의 길이는 $c_i$ 다.

노드마다 서로 다른 데이터가 하나씩 있고, $j$ 번 노드에 있는 데이터의 크기는 $s_j$ 다. 사용자는 원하는 데이터를 원하는 노드로 전송한다. 전송 비용은 데이터 크기와 전송 거리를 곱한 값이고, 데이터는 항상 최단 경로로 이동한다.

전송이 끝나면 목적지를 포함해 경로 위의 모든 노드가 그 데이터를 캐시에 저장한다. 다음 전송부터는 그 데이터의 캐시가 있는 노드 중 목적지에서 가장 가까운 노드가 데이터를 보내므로, 비용은 원래 데이터 크기와 그 노드부터 목적지까지의 거리를 곱한 값이 된다. 처음에는 어느 노드에도 캐시가 없어서 $j$ 번 데이터는 $j$ 번 노드에만 있다.

사용자는 전송할 때마다 데이터와 목적지를 마음대로 고른다. 목적지에 이미 그 데이터의 캐시가 있으면 거리가 $0$ 이라서 비용도 $0$ 이다. 전송을 $m$ 번 했을 때 비용의 합이 최대 얼마인지 구하라.

입력

첫째 줄에 노드 수 $n$ 과 전송 횟수 $m$ 이 주어진다. ( $2 \le n \le 2000$ , $1 \le m \le 10^9$ )

다음 $n-1$ 개 줄에 간선의 정보가 한 줄에 하나씩 $a_i$ , $b_i$ , $c_i$ 순으로 주어진다. ( $1 \le a_i, b_i \le n$ , $1 \le c_i \le 10000$ )

다음 줄에 정수 $n$ 개가 주어진다. $j$ 번째 정수는 $j$ 번 노드에 있는 데이터의 크기 $s_j$ 다. ( $1 \le s_j \le 10000$ )

주어지는 네트워크는 항상 트리다.

출력

전송을 $m$ 번 했을 때 얻을 수 있는 비용 합의 최댓값을 한 줄에 출력한다.

예제4

예제 1
입력
```
3 2
1 2 1
2 3 2
1 10 100
```
예상 출력
```
320
```
예제 2
입력
```
2 100
1 2 1
1 1
```
예상 출력
```
2
```
예제 3
입력
```
2 1
1 2 10000
10000 10000
```
예상 출력
```
100000000
```

예제 4

입력

2 1000000000
1 2 10000
1 10000

예상 출력

100010000