A. Big binary tree [zmy]

每次修改一个点，修改其父亲所有节点的 mx[x] 值，即向下走的最大距离。查询时，我们考虑 dp 的过程，先计算两个子树的结果，然后再向上推，计算向上路径的最大长度。思路比较简单。但是代码技巧很多。

对于一个没有被更新过的节点 v ，假设其向左扩展的最大深度为x，向右扩展的最大深度为 y 。那么如果x!=y，则最长路径一定是 v−>n ，否则一定是 v 到向右扩展的最大位置。 只对询问的点存到 map 里，其他都用暴力求，实际上更快一些。 多用 map 的 count 函数 由于是二叉树，不用一般的树 dp 那样维护一个最大和次大，只用维护最大即可。找一条不过它的路径，用异或1的方式就可以了

B. Ch’s gift [zmy]

首先将所有操作变成询问。对于点权，变成一个增加点权的操作。对于查询 [L,R] ，变成两个询问 [1,L−1] 和 [1,R] 。之后按照权值大小排序。求出树的dfs序，用树状数组维护点权。增加一个点的点权时，在 l[x] 位置增加 vi ，在 r[x] 位置增加 −vi 。对于 x−>y 这条链上的答案，通过 sum(l[lca(x,y)],l[x])+sum(l[lca(x,y)],l[y])−sum(l[lca(x,y)]) 得到。

C. CSGO [wbr]

首先将所有线段的端点和所有的敌人按照询问点的极角排好序。因为线段不会相交所以用set维护线段离原点的先后顺序就可以了。注意精度。时间复杂度 O(TQNlgN) 。

D. Dying Light[wbr]

可以看出反射的次数非常少，因此可以暴力模拟。模拟的过程中要注意利用叉积判断在哪条边上。使用On_segment函数可能会导致精度不够。

E. FFF at Valentine [zmy]

暴力求解每个点对是否能从一方到另一方。

F. Senior Pan [zmy]

将 K 点都加入到优先队列里跑 dijkstra ，图中每个点只能被访问两次，每当一个关键点到另一个关键点时更新答案。

G. Missile Interception [wbr]

二分答案。计算出答案时间时每个导弹的位置，然后就是一个裸圆交问题。

H. Numbers [zmy]

用 map 维护已经构造出来的和。如果新的数不在这个 map 中，那么一定是a数列中的一个数，并且更新一边和。

I. Senior PanⅡ[zmy]

如果 k 不为质数，那么答案一定是0。 否则，假设 k 是第i个质数，我们考虑 [1,x] 区间的答案。很容易发现，如果 k∗k>x 的话，答案最多为 k ，只需要判断一下即可。否则，k<1011−−−−√，我们可以预先筛出比它小的所有质数。接下来就是一个经典的问题，考虑 [1,x/k] 这个区间中被前 i−1 个质数筛去后剩余部分的和。用 dp 去做即可。

几个类似的题：

CodeForces 665FHdu 5877

J. Two strings [zmy]

dp。 fi,j,k 表示匹配到 si,tj 时的情况。如果 k 为1则表示当前的 ∗ 没有跳过，如果k为 0 <script type="math/tex" id="MathJax-Element-37">0</script>则表示跳过。