最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

天天百事通！LibreOJ L6210 「美团 CodeM 决赛」tree

来源：博客园


(资料图)

链接难度：\(\texttt{?}\)

有一颗 \(n\) 个点的树，每个点有权值 \(x_i\)，定义一条简单路径的权值为 \(f(a_1\to a_2\to...\to a_k)=\frac{x_{a_1}\times x_{a_2}\times ...\times x_{a_k}}{k}\)，求最小的 \(f(a_1\to a_2\to...\to a_k)\) 值。

数据范围：\(1\le n\le500000, 1\le x_i\le 10^7\ \texttt{1s 512MB}\)。

这题都做不出来我去送外卖吧.jpg

凭直觉也能想到 \(1\le x_i\le 10^7\) 肯定是唬人的，考虑只有哪些 \(x_i\) 能对答案产生贡献。

首先能想到的就是\(x_i=1\)，分子不变，分母 \(+1\)，答案肯定会小。然后就需要推式子了，设目前有连续 \(z\) 个数字 \(p(p>1,z\ge 1)\)，其左边有 \(x\) 个 \(1\)，右边有 \(y\) 个 \(1(1\le x\le y)\)，则这条路径权值为 \(\frac{p^z}{x+y+z}\)，而目前要比较的权值为 \(\frac{1}{y}\)，需使 \(\frac{p^z}{x+y+z}<\frac{1}{y}\)。

  • 两边先同时 \(\times y\times (x+y+z)\)，\(y\times p^z
  • 因为 \(x\le y\)，不妨设 \(x=y\)，\(y\times p^z<2y+z\)。
  • 两边同时减掉 \(2y\)，\(y\times (p^z-2)

可以发现只有 \(p=2,z=1\) 时成立。

那这道题就很明显了，\(x_i=1\) 可以随便选，\(x_i=2\) 至多选一个，树形 DP 即可。

设 \(Max1_u\) 为经过 \(u\) 点路径连续为 \(x_i=1\) 最多的点数，\(Max2_u\) 为经过 \(u\) 点路径上存在一个 \(2\) 其余的路径连续为 \(x_i=1\) 最多的点数（包括 \(2\)）。

方程还是挺好推的：\(Max1_u=\max\{Max1_v\}+1,Max2_u=\max\{Max2_v\}+1(x_u=1)Max2_u=\max\{\Max1_v\}+1(x_u=2)\)。转移时统计答案即可。

# include using namespace std;const int N = 500000;vector  to [N + 10];int x [N + 10];int Max1 [N + 10], Max2 [N + 10];int ans1, ans2;void DFS (int u, int fa) {if (x [u] == 1) {Max1 [u] = 1;}else if (x [u] == 2) {Max2 [u] = 1;}for (int v : to [u]) {if (v == fa) {continue;}DFS (v, u);ans1 = max (ans1, Max1 [u] + Max1 [v]);ans2 = max (ans2, max (Max1 [u] + Max2 [v], Max2 [u] + Max1 [v]));// 两段拼起来if (x [u] == 1) {Max1 [u] = max (Max1 [u], Max1 [v] + 1);Max2 [u] = max (Max2 [u], Max2 [v] + 1);}else if (x [u] == 2) {Max2 [u] = max (Max2 [u], Max1 [v] + 1);}}return ;}const int A = 500000;int main () {int n;scanf ("%d", & n);for (int i = 1; i < n; ++ i) {int x, y;scanf ("%d %d", & x, & y);to [x] .push_back (y);to [y] .push_back (x);}int Min = A;for (int i = 1; i <= n; ++ i) {scanf ("%d", & x [i]);Min = min (Min, x [i]);}if (Min > 1) {printf ("%d/1", Min);return 0;}DFS (1, 0);if ((ans1 << 1) > ans2) {// 注意这里实际上是 1 / ans1 和 2 / ans2 分母大的对应的分数更小printf ("1/%d", ans1);}else {if (ans2 & 1) {printf ("2/%d", ans2);}else {printf ("1/%d", ans2 >> 1);}}return 0;}

关键词： 实际上是