{"problem":{"name":"D. Fire","description":{"content":"_Pang_ lives on a tree with $n$ vertices. The vertices are labelled as $1, 2, \\\\dots, n$ and _Pang_ is in vertex $1$. Each vertex has a temperature. On the morning of each day after day 0, the tempera","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10247D"},"statements":[{"statement_type":"Markdown","content":"_Pang_ lives on a tree with $n$ vertices. The vertices are labelled as $1, 2, \\\\dots, n$ and _Pang_ is in vertex $1$. Each vertex has a temperature. On the morning of each day after day 0, the temperature of each vertex decreases by $1$. The temperature doesn't decrease on day 0. On the afternoon of each day, _Pang_ can travel to an adjacent vertex, provided that he is at a vertex with positive temperature and his destination vertex has a non-negative temperature. On the evening of each day, if the temperature is higher than or equal to $0$, _Pang_ can cast magic which increases the temperature of the vertex he is in by $k$. For each pair of adjacent vertices $a$ and $b$, _Pang_ can travel from vertex $a$ to vertex $b$ at most once (and from $b$ to $a$ at most once). He can choose not to travel and stay in the current vertex. \n\n_Pang_ wants to cast his magic on each vertex exactly once. He also tries to stay at vertex $1$ as long as possible, before traveling to any other city. Given the temperature of each vertex right before the morning of the day $1$, on which day must _Pang_ prepare for departing? If _Pang_ prepares on day $i$, he can cast his magic on that day and will make his first move on day $i + 1$. If he cannot cast his magic on each vertex exactly once even if he prepares for departing on the day $0$, output $-1$.\n\nThe first line contains two integers $n$ and $k$ ($2 <= n <= 100000, 0 <= k <= 1000000000$).\n\nEach of the next $n -1$ lines contains two integers $x$ and $y$, indicating an edge between vertices $x$ and $y$ ($1 <= x, y <= n$).\n\nThe $(n + 1)$-th line contains $n$ integers $a_1, a_2, \\\\dots, a_n$ — the temperature of vertex $i$ right before the morning of day $1$ ($0 <= a_i <= 1000000000$).\n\nIt's guaranteed that the input is a tree structure.\n\nIf he cannot cast his magic on each vertex exactly once, output $-1$.\n\nOtherwise, output a single integer $x$ — he must prepare for departing from vertex $1$ on day $x$. Day $1$ is the day after day $0$, and so on.\n\n## Input\n\nThe first line contains two integers $n$ and $k$ ($2 <= n <= 100000, 0 <= k <= 1000000000$).Each of the next $n -1$ lines contains two integers $x$ and $y$, indicating an edge between vertices $x$ and $y$ ($1 <= x, y <= n$).The $(n + 1)$-th line contains $n$ integers $a_1, a_2, \\\\dots, a_n$ — the temperature of vertex $i$ right before the morning of day $1$ ($0 <= a_i <= 1000000000$).It's guaranteed that the input is a tree structure.\n\n## Output\n\nIf he cannot cast his magic on each vertex exactly once, output $-1$.Otherwise, output a single integer $x$ — he must prepare for departing from vertex $1$ on day $x$. Day $1$ is the day after day $0$, and so on.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ k \\in \\mathbb{Z}_{\\geq 0} $.  \nLet $ T = (V, E) $ be a tree with $ V = \\{1, 2, \\dots, n\\} $, $ |V| = n $, and $ 1 \\in V $ is the root.  \nLet $ a_i \\in \\mathbb{Z}_{\\geq 0} $ denote the initial temperature of vertex $ i $ just before morning of day 1.  \n\n**State Dynamics**  \nLet $ t_d(v) $ be the temperature of vertex $ v $ at the start of day $ d $ (before morning decrement).  \n- $ t_1(v) = a_v $  \n- For $ d \\geq 1 $, before morning of day $ d+1 $: $ t_{d+1}(v) = t_d(v) - 1 $  \n- On afternoon of day $ d $, Pang may move from $ u $ to $ v $ if $ t_d(u) > 0 $ and $ t_d(v) \\geq 0 $, and the edge $ (u,v) $ has not been traversed in either direction.  \n- On evening of day $ d $, if $ t_d(v) \\geq 0 $ and Pang is at $ v $, he may cast magic: $ t_d(v) \\leftarrow t_d(v) + k $, **exactly once per vertex**.  \n\n**Constraints**  \n1. Each vertex must be visited and magic cast **exactly once**.  \n2. Each edge may be traversed **at most once in each direction**.  \n3. Pang starts at vertex 1 on day 1 (before any action).  \n4. He must delay departure (first move) as long as possible.  \n5. Preparation day $ x $: magic can be cast on day $ x $, first move occurs on day $ x+1 $.  \n\n**Objective**  \nFind the minimal day $ x \\in \\mathbb{Z}_{\\geq 0} $ such that:  \n- Pang can cast magic on all $ n $ vertices exactly once, following movement and temperature constraints,  \n- He remains at vertex 1 until day $ x $ (i.e., no move before day $ x+1 $),  \n- If no such $ x $ exists, output $ -1 $.  \n\n**Note**: Casting magic on vertex $ v $ requires $ t_d(v) \\geq 0 $ at the evening of day $ d $, and the vertex must be visited on day $ d $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10247D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}