2018-Reconquista-T57

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

== Contest Information ==

''' Petrozavodsk Winter 2014 - Ukrainian Contest '''

[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001437 Opentrains]

== 流水账 ==


== 总结 ==

=== lsmll ===
感觉要自我检讨一下，那个最小割输出方案之前做过了，但还是WA了数次，浪费了很长时间。后面的F题上下界网络流我们队没有板子，还好最后jsb想了一个经典转化过了。如果这些地方能节省一些时间的话，也许能再过一题。

=== jsb ===

最小割方案那题感觉有点悲伤……我们对最小割输方案了解得都不是很透彻，试了好几次才过……[[br]]
中间F题题目看错了，要反思一下。更神奇的是，题目看错后，lzw学长甚至还给出了一个匹配的做法诶！神奇！[[br]]
还好lsmll学长确认了一遍题意。而且我们后来三个人集火F，很快就fix完了。[[br]]
中后期有点卡，最后一个小时前一些才会做J，lzw学长的方法又很麻烦，我后来就没时间写B了……[[br]]
B题的话，本来看上去挺麻烦的，不过我比赛时细节想得很清楚了，赛后很快就过了……

=== lzw ===
J题主要是没想到用vector开数组，实际上需要的空间没那么多，而且最后我的做法也做复杂了，写了一坨屎，最后空间还炸了，实际上只要对每个点暴力做就好了。最后把写J题的时间给jsb也许能过B题，实际上我上机写的时候还没有完全想清楚。以后写代码一定要想清楚再上去写，或者在纸上写好，不耽误机位的时间。


== 补题 ==
B [jsb]

D [lsmll]

G []

H []

I []

J [lzw]


== 题解 ==
[D by lsmll]: 建树的过程用一个set维护上下圆，具体可以参考标程。然后建完树之后不用new meta题解中说的平衡树维护树形DP，显然开会地点选在带权的重心最优，设圆i的子树中的点权值和为s[i],所有点权值和为tot,圆i的关税为c[i],则第i个圆对答案贡献为c[i]*min(s[i],tot-s[i])。于是对每个点求出贡献，去掉最大的K个贡献即为答案。

Contest Information

Petrozavodsk Winter 2014 - Ukrainian Contest

Opentrains

流水账

总结

lsmll

感觉要自我检讨一下，那个最小割输出方案之前做过了，但还是WA了数次，浪费了很长时间。后面的F题上下界网络流我们队没有板子，还好最后jsb想了一个经典转化过了。如果这些地方能节省一些时间的话，也许能再过一题。

jsb

最小割方案那题感觉有点悲伤……我们对最小割输方案了解得都不是很透彻，试了好几次才过……[[br]]

中间F题题目看错了，要反思一下。更神奇的是，题目看错后，lzw学长甚至还给出了一个匹配的做法诶！神奇！[[br]]

还好lsmll学长确认了一遍题意。而且我们后来三个人集火F，很快就fix完了。[[br]]

中后期有点卡，最后一个小时前一些才会做J，lzw学长的方法又很麻烦，我后来就没时间写B了……[[br]]

B题的话，本来看上去挺麻烦的，不过我比赛时细节想得很清楚了，赛后很快就过了……

lzw

J题主要是没想到用vector开数组，实际上需要的空间没那么多，而且最后我的做法也做复杂了，写了一坨屎，最后空间还炸了，实际上只要对每个点暴力做就好了。最后把写J题的时间给jsb也许能过B题，实际上我上机写的时候还没有完全想清楚。以后写代码一定要想清楚再上去写，或者在纸上写好，不耽误机位的时间。

补题

B [jsb]

D [lsmll]

G []

H []

I []

J [lzw]

题解

[D by lsmll]: 建树的过程用一个set维护上下圆，具体可以参考标程。然后建完树之后不用new meta题解中说的平衡树维护树形DP，显然开会地点选在带权的重心最优，设圆i的子树中的点权值和为s[i],所有点权值和为tot,圆i的关税为c[i],则第i个圆对答案贡献为c[i]*min(s[i],tot-s[i])。于是对每个点求出贡献，去掉最大的K个贡献即为答案。