12th.Feb.2019
T1
-
题目大意：
给定一棵树，每个节点有一个权值。一个点可能会得到其他点的值，条件是，从这个点到1号节点的距离大于等于它到另一个点的距离，那么另一个点的值它就可以得到。输出每一个点最终的权值。
-
分析：
一个很自然的想法，1号节点到所有点的距离遍历一遍我们可以得到，然后可以从每个点出发，跑dist【x】深度，所有到达的点的权值都累加到x的答案里。显然这是一个n^2算法，不过跑不满，再加上我神经卡常加了fread和write，以及老师开时限比较宽松，艹了90分
正解该怎么做呢？先看一下数据范围，1e5。呃，好像需要NlogN的算法，或者再不济得有个N*sqrt（N）。但感觉刚才的思路没有能优化的部分了吧，貌似树形DP可以优化，比如设up【x】表示除x子树以外的点能对x造成多大的贡献，down【x】表示子树内的点能对x造成多大的贡献。写了写式子，发现如果知道down的话可以很方便的求出up数组，但是down数组怎么求真不会。可能这个算法可以写，但我比较菜。
接下来需要转化思路。一个点能到达哪些点不好求，那我们看看一个点能对哪些点产生贡献。仔细想一下，某一个点，哪些点可以到达他。设这个点为x，首先1~x这条链上是从中间点开始一直到x都可以到x。这个点深度是（d【x】+1）/2，设它为p。画画图，发现只有以p为根的这颗子树上的点可以到达x。所以我们把x的值标记到p上。这样的话，当我们做完的时候，再跑一边dfs，把标记下传，答案就算出来了。复杂度O（n）。
T2
- 真心不会，果断输入数据得了10分滚粗。
T3
- 神奇的交互题，老师说评测有些问题，我就没看。noi冬令营的时候也出了一道交互题，也没来得及看题目，下回有机会要好好写一道。
版权声明：本文为kgxw0430原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。