#2141. Travelling Trader

Travelling Trader

Travelling Trader

题目描述

2023 Canadian Computing Olympiad Day 2, Problem 2 Travelling Trader Time Limit: 2 seconds Problem Description A trader would like to make a business of travelling between cities, moving goods from one city to another in exchange for a profit. There are N cities labelled 1, . . . , N and N −1 roads. Each road joins two cities and takes one day to traverse. It is possible to reach any city from any other city using these roads. The i-th city can give a profit of pi if the trader is currently in that city and chooses to do business in that city, but this profit may only be obtained once. The trader starts by doing business in city 1 and wants to travel along the roads, visiting cities to maximize their total profit. However, the trader’s boss will get unhappy and lay off the trader as soon as the trader goes more than K days in a row without increasing their total profit. Note that the trader will take only one day to move between adjacent cities, regardless of whether the trader does business in either city. We would like to know the maximum profit the trader can make under this condition and a route that obtains this profit. Input Specification The first line of input contains two space-separated integers N and K. The next N −1 lines of input each contain two space-separated integers ui and vi (1 ≤ ui, vi ≤N, ui̸ = vi), describing a road. The last line of input contains N integers p1, . . . , pN (1 ≤pi ≤109), the profits given by choosing to do business in the corresponding city. Marks Awarded Bounds on N Bounds on K 2 ≤N ≤200 000 2 marks K = 1 2 ≤N ≤200 7 marks K = 2 2 ≤N ≤2 000 3 marks K = 2 2 ≤N ≤200 000 4 marks K = 2 2 ≤N ≤2 000 4 marks K = 3 2 ≤N ≤200 000 5 marks K = 3 Output Specification On the first line, output the maximum possible total profit. On the second line, output M (1 ≤M ≤N), the number of cities the trader does business in on an optimal route. On the third line, output M space-separated integers x1, . . . , xM, the cities the trader does business in on an optimal route in order, starting with x1 = 1. If there are multiple possible correct outputs, any correct output will be accepted. Sample Input 1 4 1 1 2 1 3 2 4 3 1 4 1 Output for Sample Input 1 7 2 1 3 Explanation of Output for Sample Input 1 On day 1, the trader starts by doing business in city 1, making a profit of 3. On day 2, the trader moves to city 3 and does business there, making a profit of 4. At this point, the trader cannot reach another city in which they have not done business before getting laid off, so their total profit is 7. Sample Input 2 5 2 1 2 1 3 2 4 2 5 3 1 4 1 5 Output for Sample Input 2 14 5 1 4 5 2 3 Explanation of Output for Sample Input 2 The trader can make a profit in every city by visiting them in the order 1, 2, 4, 2, 5, 2, 1, 3. Note that the trader strategically delays doing business in city 2 to ensure they do not go more than 2 days without making a profit.

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

4 1
1 2
1 3
2 4
3 1 4 1
7
2
1 3

样例 2

5 2
1 2
1 3
2 4
2 5
3 1 4 1 5
14
5
1 3 2 4 5