Day 1 A 树

给出一棵个点的树,第个点有权值,现在需要支持次操作:

  • 第一种操作格式为 “1”,表示询问从出发的简单路径,经过的点权值之和的最大值;
  • 第二种操作格式为 “2”,表示将修改为

如果没有修改操作,那么可以换根 DP。

如果询问的固定,那么可以求出 DFS 序,然后线段树维护子树距离 max。

建出点分树。从出发的路径,一定是经过点分树上的某个父亲,然后延伸向另一个与不同的连通块。修改一个点的权值,会修改若干条路径。不过我们已经将问题转化为了点分树连通块里以重心为端点的路径信息问题——也就是定了根。那么修改一个点权,就会修改一个子树的路径的权值。自然想到线段树维护子树 max。再用一个堆维护子连通块的 max 集合即可。修改的时候暴力跳父亲修改即可。

时间复杂度

Day 1 B Numazu 的蜜柑

给出一棵个点的树,的点权是。给出常数,求有多少对满足

  • 的祖先。

是质数。

当时谁写的 nt 题面,不告诉我是质数。后来才改的。

既然是质数,就可以随便折腾了。变换一下得到

,则原式化为

解得

首先得是二次剩余,不然无解。然后就 DFS 记个 map 就行了。

Day1 C 星际迷航

在一个维空间中,给你个点。初始时你在原点。每次你可以选择个点中的一个,然后跳到关于它的对称点上去。给你一个模数。有次询问。

每次询问给出一个点。问你能否跳到一个点使得,也就是每一维都与在模意义下同余。

注意,原点不一定可以用于跳转。