{"problem":{"name":"D. Diameter of a Tree","description":{"content":"Given a weighted tree $T_0$, we define its diameter as the length of the longest path between two vertices on it, where the length of a path is equal to the sum of weights of edges in the path. If th","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":10000,"memory_limit":1048576},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10195D"},"statements":[{"statement_type":"Markdown","content":"Given a weighted tree $T_0$, we define its diameter as the length of the longest path between two vertices on it, where the length of a path is equal to the sum of weights of edges in the path.\n\nIf the tree stretches like a spider or a yawning tiger, its diameter will change. Let's use $T_i$ to denote the state of the tree after $i$ seconds, at which time the weight of each edge has been increased by exactly $i$ units from $T_0$.\n\nYou will be presented with several different queries, and you should calculate the tree's diameter at some specified time for each query.\n\nThe input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $60$.\n\nFor each test case, the first line contains two integers $n$ and $m$ indicating the number of vertices in the tree and the number of given queries respectively, where $2 <= n <= 2 times 10^5$ and $1 <= m <= 2 times 10^5$.\n\nEach of the following $(n -1)$ lines contains three integers $u, v$ and $w$ which represent an edge in the original tree between the $u$-th vertex and the $v$-th one of weight $w$, where $1 <= u, v <= n$, $u != v$ and $1 <= w <= 10^8$.\n\nEach of the following $m$ lines describes a query containing only one integer $k$ that asks you to calculate the diameter of the tree $T_k$, where $0 <= k <= 10^9$.\n\nWe guarantee that the sum of $n$ in all test cases is no larger than $10^6$, and the sum of $m$ in all test cases is no larger than $10^6$ as well.\n\nFor each test case, output a line containing \"_Case #x:_\" (without quotes) at first, where _x_ is the test case number starting from $1$.\n\nThen output $m$ lines corresponding to all queries. The $i$-th line of them contains an integer indicating the answer to the $i$-th query.\n\nIn the second sample case:\n\n## Input\n\nThe input contains several test cases, and the first line contains a positive integer $T$ indicating the number of test cases which is up to $60$.For each test case, the first line contains two integers $n$ and $m$ indicating the number of vertices in the tree and the number of given queries respectively, where $2 <= n <= 2 times 10^5$ and $1 <= m <= 2 times 10^5$.Each of the following $(n -1)$ lines contains three integers $u, v$ and $w$ which represent an edge in the original tree between the $u$-th vertex and the $v$-th one of weight $w$, where $1 <= u, v <= n$, $u != v$ and $1 <= w <= 10^8$.Each of the following $m$ lines describes a query containing only one integer $k$ that asks you to calculate the diameter of the tree $T_k$, where $0 <= k <= 10^9$.We guarantee that the sum of $n$ in all test cases is no larger than $10^6$, and the sum of $m$ in all test cases is no larger than $10^6$ as well.\n\n## Output\n\nFor each test case, output a line containing \"_Case #x:_\" (without quotes) at first, where _x_ is the test case number starting from $1$.Then output $m$ lines corresponding to all queries. The $i$-th line of them contains an integer indicating the answer to the $i$-th query.\n\n[samples]\n\n## Note\n\nIn the second sample case:  the diameter of $T_0$ is $105$, which is the length of the path $1 -2 -3$; and  the diameter of $T_5$ is $117$, which is the length of the path $1 -2 -4 -5$.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ W \\in \\mathbb{Z}^+ $ be the number of players, $ B \\in \\mathbb{Z}^+ $ the length of each sequence.  \nLet $ S = \\{s_1, s_2, \\dots, s_W\\} $ be a set of $ W $ distinct binary strings over $ \\{H, T\\} $, each of length $ B $.  \n\nLet $ \\mathcal{F} $ be the set of all infinite sequences of coin flips (each flip independently $ H $ or $ T $ with probability $ \\frac{1}{2} $).  \nFor each $ f \\in \\mathcal{F} $, define $ \\tau(f) = \\min \\{ n \\in \\mathbb{N} \\mid \\exists i \\in \\{1,\\dots,W\\} \\text{ s.t. } s_i \\text{ appears as contiguous substring in } f_1 f_2 \\dots f_n \\} $.  \n\n**Constraints**  \n1. $ 1 \\leq W \\leq 10 $  \n2. $ 1 \\leq B \\leq 30 $  \n3. Each $ s_i \\in \\{H, T\\}^B $  \n\n**Objective**  \nCompute the expected value:  \n$$\n\\mathbb{E}[\\tau] = \\sum_{f \\in \\mathcal{F}} \\tau(f) \\cdot \\mathbb{P}(f)\n$$  \nwhere $ \\mathbb{P}(f) = 2^{-\\tau(f)} $ for the prefix of $ f $ of length $ \\tau(f) $, and the sum is over all finite prefixes that cause a match.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10195D","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}