{"problem":{"name":"H. city safety","description":{"content":"Country X is a prosperous free-trade country, which has $n$ cities connected by $n -1$ bidirectional roads. Although country X has been very stable, businessmen are generally very sensitive to the saf","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CFH"},"statements":[{"statement_type":"Markdown","content":"Country X is a prosperous free-trade country, which has $n$ cities connected by $n -1$ bidirectional roads. Although country X has been very stable, businessmen are generally very sensitive to the safety of cities. They hope country X can strengthen public security forces to ensure the safety of cities.\n\nIn addition, businessmen are also concerned about the safety of the surrounding areas. Therefore, if the security force in a city is strengthened, but the security force in the nearby cities are not strengthened, they will still be worried about the threat in nearby cities.\n\nFormally, to strengthen the security force in city $i$, a cost of $w_i$ should be paid. Such effort is not in vain, as more businessmen will be attracted and country X will benefit from it. If every city with a distance from city $i$ less or equal to $p$ is strengthened, the city $i$ will gain $v_p$ more income than before. (if more than one $p$ satisfy the condition, only the maximum one is considered.)\n\nNow you, as the country's officer, are appointed to deal with this problem. Your goal is to get the maximum benefit (the increased income minus the cost of strengthening the security force).\n\nThe first line contains one integer $n$ ($1 <= n <= 200$), representing the number of cities in country X.\n\nThe second line contains $n$ integers $w_1, w_2, \\\\\\\\cdots, w_n$ ($1 <= w_i <= 10^5$), representing the cost of strengthening security force in city $i$.\n\nThe third line contains $n$ integers $v_0, v_1, \\\\\\\\cdots, v_{n -1}$ ($1 <= v_i <= 10^5, \" \"v_i <= v_{i + 1}$), representing the benefit as stated above.\n\nNext $n -1$ lines each contains two integers $u, v$ ($1 <= u, v <= n, \" \"u eq.not v$), representing that there is a bidirectional road between city $u$ and $v$.\n\nThe only line contains an integer, indicating the maximum benefit.\n\n## Input\n\nThe first line contains one integer $n$ ($1 <= n <= 200$), representing the number of cities in country X.The second line contains $n$ integers $w_1, w_2, \\\\\\\\cdots, w_n$ ($1 <= w_i <= 10^5$), representing the cost of strengthening security force in city $i$.The third line contains $n$ integers $v_0, v_1, \\\\\\\\cdots, v_{n -1}$ ($1 <= v_i <= 10^5, \" \"v_i <= v_{i + 1}$), representing the benefit as stated above.Next $n -1$ lines each contains two integers $u, v$ ($1 <= u, v <= n, \" \"u eq.not v$), representing that there is a bidirectional road between city $u$ and $v$.\n\n## Output\n\nThe only line contains an integer, indicating the maximum benefit.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"疯狂科学家德克斯特在进行分子化学实验。今天，他试图用 #cf_span[n] 个原子构建一个单一分子。\n\n众所周知，分子由若干原子组成，其中某些原子对之间通过化学键相连。每个原子具有一个价态值——表示该原子能与其他原子形成的键的数量。一个原子可以与另一个原子形成*一个或多个*键，但不能与自身形成键。每个原子实际形成的键数必须等于其价态。分子必须是*连通的*，即任意两个原子之间都存在一条由化学键构成的路径相连。\n\n德克斯特已知这 #cf_span[n] 个原子各自的价态。请帮他找出一个可以用这些原子构建的分子，或判断这是不可能的。\n\n输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 5000])，表示原子的数量。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[di] (#cf_span[1 ≤ di ≤ 109])，其中 #cf_span[di] 表示第 #cf_span[i] 个原子的价态。\n\n如果可以用给定的原子构建一个连通分子，则第一行输出 \"_Yes_\"。然后输出 #cf_span[n - 1] 行，其中第 #cf_span[i] 行必须包含 #cf_span[n - i] 个用空格分隔的整数。第 #cf_span[i] 行中的第 #cf_span[j] 个数表示原子 #cf_span[i] 与原子 #cf_span[i + j] 之间的键的数量。原子按输入顺序编号为 1 到 #cf_span[n]。如果有多个解，输出任意一个即可。\n\n如果这样的分子不存在，则在单独一行输出 \"_No_\"（不带引号）。\n\n## Input\n\n输入的第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 5000])，表示原子的数量。第二行包含 #cf_span[n] 个用空格分隔的整数 #cf_span[di] (#cf_span[1 ≤ di ≤ 109])，其中 #cf_span[di] 表示第 #cf_span[i] 个原子的价态。\n\n## Output\n\n如果可以用给定的原子构建一个连通分子，则第一行输出 \"_Yes_\"。然后输出 #cf_span[n - 1] 行，其中第 #cf_span[i] 行必须包含 #cf_span[n - i] 个用空格分隔的整数。第 #cf_span[i] 行中的第 #cf_span[j] 个数表示原子 #cf_span[i] 与原子 #cf_span[i + j] 之间的键的数量。原子按输入顺序编号为 1 到 #cf_span[n]。如果有多个解，输出任意一个即可。如果这样的分子不存在，则在单独一行输出 \"_No_\"（不带引号）。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of atoms.  \nLet $ \\mathbf{d} = (d_1, d_2, \\dots, d_n) \\in \\mathbb{Z}^n $ be the vector of valences, where $ d_i \\geq 1 $ is the valence of atom $ i $.  \n\nLet $ A = (a_{ij}) \\in \\mathbb{Z}^{n \\times n} $ be a symmetric matrix with $ a_{ii} = 0 $ for all $ i $, and $ a_{ij} = a_{ji} \\geq 0 $ for $ i \\neq j $, representing the number of bonds between atom $ i $ and atom $ j $.  \n\n**Constraints**  \n1. **Degree constraint**: For each $ i \\in \\{1, \\dots, n\\} $,  \n   $$\n   \\sum_{j=1}^{n} a_{ij} = d_i\n   $$  \n2. **Connectivity**: The graph $ G = (V, E) $ with vertex set $ V = \\{1, \\dots, n\\} $ and edge multiplicities $ a_{ij} $ is connected.  \n3. **Total valence parity**: The sum $ \\sum_{i=1}^n d_i $ is even (necessary for existence of any multigraph).  \n\n**Objective**  \nDetermine if there exists a symmetric matrix $ A $ satisfying the above constraints. If yes, output such a matrix in lower-triangular form (excluding diagonal): for each $ i \\in \\{1, \\dots, n-1\\} $, output $ a_{i,i+1}, a_{i,i+2}, \\dots, a_{i,n} $. Otherwise, output \"No\".","is_translate":false,"language":"Formal"}],"meta":{"iden":"CFH","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}