CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

======= 2020/05/16-2020/05/22周报 =======
====== 团队训练 ======
2020.5.20 [[2018-2019 ACM-ICPC, Asia Nanjing Regional Contest]]

====== 个人训练======
====== 李元恺 ======
摸了一周
====== 姜维翰 ======
===== 专题 =====
没有专题
===== 比赛 =====
没有比赛
===== 题目 =====

====== 袁熙 ======

===== 专题 =====
没有专题
===== 比赛 =====
没有比赛
===== 题目 =====
补补题：[[http://codeforces.com/contest/1303/problem/G|题目链接]]

题意：求$n(1.5*10^5)$个点的树上路径$p_1 ... p_k$使这些点的权值$a_1 ... 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[[http://codeforces.com/contest/1303/problem/G|题目链接]]

CVBB ACM Team

用户工具

站点工具

页面工具