究极套路题，挺有意思的 \(qwq\) 。
首先我们记一些东西。
记 \(f(x)\) 为 \(x\) 子树中选出的不交路径权值和最大是多少。
记 \(g(x)\) 为 \(x\) 子树外的不交路径权值和最大是多少。
如果有了这两个东西那么答案就很好计算了。
那么 \(f(1)\) 实际上就是 \(W(U)\) 。
\(---------------------------------\)
考虑如何计算 \(f\) ，算是一个比较典的套路。
我们记 \(sum_u=\sum\limits_{t\in son_u} f_t\)
然后我们考虑把路径挂到 \(lca\) 上。
对于一条路径 \((x_i,y_i,w_i)\) ，假设他的 \(lca\) 为 \(u\) ，那么他对 \(u\) 的贡献是 \(w_i+\sum \limits_{j\in x_i\to y_i(j\not=u)} sum_j-f_j+sum_u\)
相当于把这条路径给去掉后，剩下各个连通块的最大值之和。
最后对这个东西取一个 \(\max\) 就可以得到 \(f_u\)
而这个东西维护的话，用树剖是很容易解决的，可实际上单点加链求和，可以转换成子树加单点求和，这部分复杂度是 \(O(n\log n)\) 的。
\(---------------------------------\)
接下来考虑如何求 \(g\) 。
首先 \(g(1)=0\) 这是显然的，考虑如何从 \(u\) 递推到 \(v\) 。
有三种情况。
-
\(u\) 没有被任何路径经过，\(g_v=g_u+sum_u-f_v\) ，这个也是显然的。
-
\(u\) 被某一条路径经过，记作 \(x_i,y_i,w_i\) ，且 \(lca(x_i,y_i)=u\) ，那么也就是说这条路径经过了 \(u\) 的某两个儿子，记作 \(v_1,v_2\) 。那么这条路径的贡献就是 \(g_u+w_i+\sum \limits_{j\in x_i\to y_i(j\not=u)} sum_j-f_j+sum_u-f_v\) ，那么这个东西可以贡献给除了 \(v1,v2\) 外 \(u\) 的儿子。
-
\(u\) 被某一条路径经过，记作 \(x_i,y_i,w_i\) ，而 \(lca(x_i,y_i)\not =u\) ，假设 \(lca(x_i,y_i)=Q\) 那么也就是说这条路径经过了 \(u\) 的某一个儿子，记作 \(v_1\) ，这条路径的贡献就是 \(g_Q+w_i+\sum \limits_{j\in x_i\to y_i(j\not=u)} sum_j-f_j+sum_u-f_v\) ，然后可以贡献给除了 \(v_1\) 以外的儿子，而且这是对于 \(x_i\to y_i\) 外的路径都是如此，可以用线段树单点修改，而对于查询就查询自己子树外的最大值即可。
具体二操作如何实现，我们按照 \(w_i+\sum \limits_{j\in x_i\to y_i} sum_j-f_j\) 排序，然后枚举找到第一个合法的位置，暴力找就可以了，为什么这样复杂度是对的呢，因为每条路径最多会失败两次，所以实际上是对的。
这部分复杂度也是 \(O(n\log n)\) 的。
\(---------------------------------\)
现在知道了 \(f,g\) 考虑如何计算贡献。
考虑答案形状实际上就是若干个 \(f\) 加上一个 \(g\) ，也就是 \(\sum \limits_{j\in x_i\to y_i(j\not=u)} sum_j-f_j+sum_u+g(fa[lca(x_i,y_i)])+w_i\) 。
容易发现 \(\sum \limits_{j\in x_i\to y_i(j\not=u)} sum_j-f_j+sum_u+g(fa[lca(x_i,y_i)])\) 肯定是 \(\le f_1\) 的。
我们令 \(f_1-\sum \limits_{j\in x_i\to y_i(j\not=u)} sum_j-f_j+sum_u+g(fa[lca(x_i,y_i)])\) ，就可以得到 \(w_i\) 第一个不贡献的位置，也就是临界点，然后加 \(1\) 就是答案。
考虑拆贡献。
每个 \(f_u\) 被贡献，当且仅当 \(fa_u\) 被选了，而 \(u\) 没有被选择，考虑容斥算这个东西的方案数。
先记 \(sz_i\) 表示 \(i\) 的子树大小 \((n\times n-2\times sz_i\times (n-sz_i)-\prod\limits_{t\in son} sz_t^2\times (n-sz_u)^2)\) ，这个就是方案数。
而 \(g\) 也同理。
这个东西复杂度是 \(O(n)\) 的。
总复杂度是 \(O(n\log n)\) ，解决该题。
标签：sz,limits,P5642,路径,人造,解题,复杂度,lca,sum From： https://www.cnblogs.com/ddl1no2home/p/17795472.html