Haymouth the cow and Moosa, his friend, were just eating bananas togther, when all of a sudden, they both broke out laughing uncontrollably. Neither of them knew why they were laughing, only that they couldn't stop no matter how they tried.
It's not funny! Haymouth was laughing so hard all of his four stomachs hurt badly. Fortunately for them, the doctors at the Moospital were able to figure out what was going on and stop them from laughing.
When two cows who are friends eat bananas together, there is a chance that they will catch banana fever. Haymouth, knowing all too well how painful banana fever is, wants to prevent this from ever happening again. A cownference was held to decide on the best course of action, and he suggested that no two cows who are friends should be allowed to eat bananas on the same day. There were violent objections, but they eventually agreed on the condition that the cows allowed to eat bananas are selected every day to maximise total cow happiness.
Cows have a very efficient social structure. Every cow can get a message to any other cow just by word of mouth between friends. However, they prefer to spend their time eating bananas, so no cow will make friends with another cow he can already communicate with.
As you already know, cow happiness is equal to the number of bananas eaten. Given the friendships between N cows (labelled from 0 to N - 1), and with the knowledge that cow i will eat Bi bananas today if he is allowed to, find the maximum total cow happiness for today and choose the lucky cows that will be allowed to eat bananas.
The first line will contain the integer N (1 ≤ N ≤ 1,000,000).
N - 1 lines follow, each containing two integers a and b (0 ≤ a, b < N). This means cow a is friends with cow b.
The last line will contain N integers Bi (0 ≤ Bi ≤ 1,000).
The first line of the output should contain one integer: the maximum total cow happiness for today.
The second line of the output should contain one integer M: the number of cows allowed to eat bananas today.
The third line of the output should contain M integers Ci (0 ≤ Ci ≤ N) the labels of the cows allowed to eat bananas today, in any order. If there is more than one set of cows that will give the same maximum total cow happiness, output any one.
Subtask 1 (9%): 1 ≤ N ≤ 20.
Subtask 2 (17%): 1 ≤ N ≤ 1000.
Subtask 3 (25%): 1 ≤ N ≤ 100,000, no cow has more than two friends.
Subtask 4 (46%): 1 ≤ N ≤ 100,000.
Subtask 5 (3%): 1 ≤ N ≤ 1,000,000.
Subtask 6 (0%): Sample testcases.
5 0 1 1 2 1 3 3 4 1 32 2 4 10
42 2 1 4
Selecting cow 1 and 4 will yield a total cow happiness of B1 + B4 = 32 + 10 = 42. This is optimal.
| Subtask | Score |
|---|---|
| 1 | 9 |
| 2 | 17 |
| 3 | 25 |
| 4 | 46 |
| 5 | 3 |
| 6 | 0 |