30480번 - Elevated Profits 다국어

문제

Marina, a digital influencer who loves traveling the world, is embarking on a promotional tour for a women’s clothing brand called W²M (From Woman to Woman Marina). Marina’s journey takes her through $N$ cities in Latin America, each with its unique charm, and identified with a distinct integer from 1ドル$ to $N,ドル called its popularity index.

To facilitate Marina’s travels, W²M has provided her with $N - 1$ transfers, connecting pairs of cities in a way that guarantees accessibility to all $N$ cities. Marina can traverse these connections as many times as she pleases.

Marina’s mission is to showcase the brand’s dresses in each of the $N$ cities, with a twist. Each time she visits a city for the first time, she must select a dress she hasn’t worn before and capture the city’s essence in a social media post. Every new picture she shares attracts followers, creating anticipation for the next one. The anticipation value for her first picture is 1ドル,ドル and it increments by 1ドル$ for each subsequent picture.

Marina can revisit any city as often as desired, but a new picture must only be posted on her initial visit to a city. Her goal is to maximize the profit of her tour, which is computed as the sum of the anticipation value of each picture multiplied by the popularity index of the city where the picture is taken. More precisely, let $p_i$ be the popularity index of the city where the $i$-th picture is taken. With this information, the profit can be calculated as

$$\sum_{i=1}^{N}{i \times p_i} = 1 \times _1 + 2 \times p_2 + \cdots + N \times p_N$$

Now, Marina seeks your assistance. Given that the tour has to start in city $p_1 = R,ドル your task is to help Marina determine the maximum profit she can achieve by strategically planning the order of her city visits.

입력

The first line contains two integers $N$ (1ドル ≤ N ≤ 3 \times 10^5$) and $R$ (1ドル ≤ R ≤ N$), indicating respectively the number of cities and the initial city of the tour.

Each of the next $N - 1$ lines contains two integers $U$ and $V$ (1ドル ≤ U, V ≤ N$ and $U \ne V$), indicating that there is a transfer between cities $U$ and $V$. It is guaranteed that it is possible to reach every city by using the transfers.

출력

Output a single line with an integer indicating the maximum profit Marina can achieve on her promotional tour.

제한

힌트