2020.5.20 2018-2019 ACM-ICPC, Asia Nanjing Regional Contest

摸了一周

没有专题

没有比赛

没有专题

没有比赛

补补题：题目链接

题意：求$n(1.5*10^5)$个点的树上路径$p_1 \ldots p_k$使这些点的权值$a_1 \ldots a_k$的加权和$\sum_{i=1}^k ia_i$最大

题目涉及到路径，可以考虑点分，点分时记录

考虑从某一点出发的所有路径，对其中任一条路径u，记$s1=\sum_{i=1}^k a_i,s2=\sum_{i=1}^k ia_i$,

则其他无公共点的路径v与他组成的路径的加权和可以表示为$S=s2_v+s2_u+s1_u*l_v/s1_v*l_u (路径出发的方向影响)，l为路径长度$

所以对u，需要找到使S最大的路径v。

看到上述公式表达式类似直线，可以考虑点分后用凸包或李超线段树来维护表达式对应的直线；上述量可以在点分治中记录，复杂度O(nlogn^2))

代码：咕咕中orz

同本周题目：cf1303G题目链接