SCOI Online

Day 1 A 树

给出一棵$n$个点的树，第$i$个点有权值$a_i$，现在需要支持$m$次操作：

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

$1\le n\le 10^5,1\le m\le 10^5,|a_i|,|v|\le 10^4$。

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

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

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

时间复杂度$O((n+m)\log ^2n)$。

Day 1 B Numazu 的蜜柑

给出一棵$n$个点的树，$u$的点权是$a_u$。给出常数$p,A,B$，求有多少对$(u,v)$满足

• $v$是$u$的祖先。
• $a_u^2+Aa_ua_v+Ba_v^2\equiv 0\pmod p$。

$n\le 10^5,3\le p\le 10^{16},0\le A<p,0<B<p,0<a_i<p$。$p$是质数。

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

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

$$\frac{a_u}{a_v}+A+B\frac{a_v}{a_u}=0\pmod p$$

令$x=\frac{a_u}{a_v}$，则原式化为

$$x+A+\frac{B}{x}=0\pmod p$$

解得

$$x=\frac{-A\pm \sqrt{A^2-4B}}{2} \pmod p$$

首先$A^2-4B$得是二次剩余，不然无解。然后就 DFS 记个 map 就行了。

Day1 C 星际迷航

在一个$m$维空间中，给你$n$个点$p_i=(p_{i,1},p_{i,2},\cdots,p_{i,m})$。初始时你在原点。每次你可以选择$n$个点中的一个，然后跳到关于它的对称点上去。给你一个模数$P$。有$Q$次询问。

每次询问给出一个点$u=(u_1,\cdots,u_m)$。问你能否跳到一个点$v=(v_1,\cdots,v_m)$使得$\forall 1\le i\le m, v_i=u_i\pmod P$，也就是每一维都与$u$在模$P$意义下同余。

$n,q\le 10^5,m\le 10,P\le 10^8$。

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