http://vfleaking.blog.uoj.ac/blog/38

「UR #2」猪猪侠再战括号序列

猪猪侠大神太厉害了

下面俩题怎么这么恶心T T

「UR #2」跳蚤公路

负环能影响一个点v当其与1，v都连通，这个用floyd就好

不等式取整要手写

虽然分析了那个式子写起来还是蛋疼

每个环每个系数k，枚举j，取整范围求并

就能得出所能影响的点的x取值范围，x<=l或x>=r

一个点的x被许多这样的取整范围限定T T

将区间排序一下扫一遍得去其范围即可。。。

「UR #2」树上GCD

题意

定义树上的一条路径\(a,b\)的权值，设a为深度小的点， LCA 为\(a,b\)的最近公共祖先

若a为b的祖先，权值为\(dis(a,b)\)，否则权值为\(gcd(dis(a,LCA),dis(b,LCA))\)，输出路径权值为i的路径数

\(1<=i<n\)

题解

算法一

枚举两个点 \(u,v\)，用 \(O(\log n)\) 时间计算 LCA 和 gcd，并更新答案。复杂度 \(O(n^2\log n)\)。

也可以枚举 LCA，往子树方向进行 bfs，由于计算 gcd 是 \(O(\log n)\)的，所以复杂度还是 \(O(n^2\log n)\)。

可以获得 10 分。

算法二

随机生成的树的树高为 \(O(\log n)\)。

枚举 u，计算以 u 为 LCA 的所有点对的答案。计算时对 \(u\) 的子树 dfs，统计出每个深度 \(h\) 上的结点数量 \(cnt[h]\)。枚举深度 \(h_1, h_2\)，并将 \(cnt[h_1]\cdot cnt[h_2]\) 累加到 \(ans[\gcd(h_1,h_2)]\) 中。注意还需把同一个子树内的多余计算给减掉。这样，统计答案的复杂度是 \(O(deg[u]\cdot \log^2 n)\)，总和是\(O(n \log^2 n)\)。另外，每个点最多被DFS到 \(O(\log n)\) 次，所以dfs的总复杂度是 \(O(n\log n)\)。

于是总复杂度 \(O(n\log^2 n)\)。可以获得 30 分。

算法三

我们可以把问题转化为，对于每个 d，求出 \(\gcd(h_1,h_2)\) 是 d 的倍数的点对的数量，然后用个\(O(n\log n)\)的暴力就能得出答案。

第4个数据点中，从根结点挂下来若干条链，长度分别为 \(h_1,\cdots,h_k\)。\(u,v\) 属于同一条链的情况可以方便计算；\(u,v\) 不在同一条链上时，LCA即为根结点。对于某个 d，第 i 条链中高度为 d 的倍数的点有 \(\left\lfloor h_i/d\right \rfloor\) 个；我们要统计 k 条链中选出两条来的乘积总和，可以利用恒等式 \((x_1+\cdots+x_k)^2=x_1^2+\cdots + x_k^2 +2\sum_{1\leq i < j\leq k}x_i x_j\) 求得。

其实维护前缀和就行了TAT

复杂度\(O(n\log n)\)。可以获得 40 分。

算法四

考虑点分治，每次取出当前树的中心 c。考虑所有 \(u \rightarrow LCA(u,v) \rightarrow v\) 的路径经过 c 的点对 \((u,v)\) 所产生的贡献，共有两种情况：

1.\(u,v\) 均在 c 的子树内，此时 LCA 即为 c。和算法三类似，只是第 i 条链中高度为 d 的倍数的点的数量需要在处理出 cnt 数组后花 \(hi/d\) 的时间统计，所以复杂度是\(O(n \log n)\)。

2.u 在 c 的子树内，而 v 不在。我们把当前树的根节点记为 root，\(father[c]\) 到 root 的路径为 \(father[c]=a_1,a_2,\cdots,a{k-1},a_k=root\)。记 c 下面的子树高度为 H，\(a_i\) 旁边伸出的子树（即不包含 \(a_{i-1}\) 的子树的高度为 \(h_i\)。枚举 \(a_i=LCA(u,v)\)，那么 v 位于 \(a_i\) 旁边的子树中，然后我们仍然枚举 d，用 \(h_i/d\) 的时间求出 \(a_i\) 子树中高度为 d 的倍数的结点数量；但我们还需要知道 c 的子树中有多少点相对于 \(a_i\) 的高度是 d 的倍数，与前者直接相乘计入答案，也就是说我们要在 c 子树的 cnt 数组中查询下标间隔为 d 的子序列中的元素之和\((0<d<=h_i)\)。注意到间隔为 d 时，至多只有 d 种这样的子序列，我们对重复查询进行记忆化。于是对于 \(d<\sqrt{H}\)，查询的复杂度不超过 \(d\cdot H/d=H\)，总共是 \(\sqrt{H}\cdot H\)；对于 \(d>\sqrt{H}\)，单次查询的复杂度为 \(H/d<\sqrt{H}\)。

这里可能还要考虑 u 在 c 的子树内，v = \(a_i\)。由于\(a_i\)到 c 的距离是从1开始的一段区间，对于\(ans[i] (0<i<=H+dis(a_i,c))\)的贡献是 cnt 的一段区间和，随着 i 的增长这个区间左右端点单调递增，所以复杂度是\(O(n)\)。

所以一层分治的复杂度是 \(O(n\sqrt{n})\)的。根据主定理，总复杂度就是\(O(n\sqrt{n})\),可以通过所有测试点获得 100 分。

10分

100分