圆方树可以解决仙人掌或一类无向图问题。

建树

通过 tarjan 缩点双为方点，原来的点为圆点。每个圆点连边到自己所属的点双方点，跨点双的圆点连边转换为圆方点之间的连边。

参考代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

struct edge {
    int tot, flag, hed[N], nxt[M], to[M];
    edge () { tot = 2; }
    void link(int u, int v) {
        nxt[tot] = hed[u], to[tot] = v, hed[u] = tot++;
        nxt[tot] = hed[v], to[tot] = u, hed[v] = tot++;
    }
} G1, G2;

void tarjan(int u, int father) {
    ++base, dfn[u] = low[u] = ++tim, ins[u] = 1, stk[++top] = u;
    for (int i = G1.hed[u], v = G1.to[i]; i; i = G1.nxt[i], v = G1.to[i])
        if (v != father) {
            if (!dfn[v]) {
                tarjan(v, u), low[u] = std::min(low[u], low[v]);
                if (low[v] >= dfn[u]) {
                    G2.link(u, ++tot), ++val[tot]; int x;
                    do {
                        x = stk[top--], ins[x] = 0;
                        G2.link(x, tot), ++val[tot];
                    } while (x != v);
                }
            } else if (ins[v]) low[u] = std::min(low[u], dfn[v]);
        }
}

• 需要注意的是，根节点所在的点双的方点并不会创建，在大多数情况下，这并不会有影响，可根据题目的需要取舍。

性质

由此我们可以发现一些有趣的性质：

• 现在总点数与原来的点数同阶，现在的总边数与原来的总边数同阶
• 所有边都是圆点和方点之间的连边，即不存在圆圆边或方方边

T1、T3 的思路基本都成型但是由于自己傻逼最后一个都没调出来。

LCM

考虑一个数最多被分解为一个大于 $\sqrt {\max a_i}$ 的质数和一些小于 $\sqrt {\max a_i} $ 的质数的乘积。考虑小于的部分，最多有 4320 种状态，我们可以用一种简单背包的方法统计出每一种值的个数。对于大于的部分，相当于我们给上一步统计的个数的时候给个数加上一个权值。通过一些简单的处理避免超过 $\sqrt { \max a_i }$ 的质数被重复计算。理论复杂度 $O(n \times 4320 \times (\log n + \log 4320))$ 。

Xor

不知道为什么出题人要把题意搞的这么迷。我们直接把边权异或到两个端点上，计算割的价值就是一边的点的权值的异或和。考虑贪心，把点按照权值从大到小排序，利用线性基维护会不会产生 $0$ ，不会就加上价值，否则减掉即可。

Lis

考虑把从左到右的最长上升子序列转变为从右到左的最长下降子序列，这样每次操作最多影响十棵树。树套树（树状数组套权值线段树）维护一个后缀高度大于指定值的 dp 值的最大值，每次暴力重算那十棵树即可。复杂度 $O(n \log^2 n \times 10)$ 。需要注意的是需要动态开的节点个数可能会很多，一定要开够。

T3 难度并不大，但是由于时间分配问题 + 出题人数据有锅必须输出行末空格否则 WA 导致本来会做的 T3 没有 AC 。

迷路

对于每一个点，建出最短路树，对于每一条非树边，如果他的两个节点在根节点的不同子树内，那么可以对答案产生贡献。

宝藏

类欧优化的数学题，不会。

蛋糕

THUPC 原题的强化版，由 $4$ 维变成 $n$ 维。每一维变成一个多项式分治 NTT 即可。

根据小学我们就学过的一个简单公式，如果 $x = \prod p_i ^ { a_i } $ 那么 $x$ 因子个数为 $\prod a_i + 1$ 。因此我们需要维护查询的区间内每一个质数的和。

考虑把原来的数分解，这一步我们只需要预处理出小于 $ \sqrt { \max {a_i} }$ 的质数即可。然后对于每个数 $ a_i $ 依次判断小于 $ a_i $ 的质数。复杂度 $ O( \frac {n \sqrt{\max{a_i}}} {\log n} )$ ，实际情况下表现非常优越。或者采用 Pollard-Rho 算法优化为 $ n \times \sum { a_i^{ 1 / 4 } }$ ，但实现会较为复杂而且没有必要。

接下来考虑分解出的质数如何处理，如果直接放在一起去莫队的话复杂度是 $ O(n \sqrt n \log n) $ ，如果常数不优秀的话会 TLE 。我们考虑一个优化方式，对于大小在前 $\sqrt n$ 个的范围内的质数，预处理出个数，前缀和统计，不参与莫队，其余分解出的质数参与莫队，可以证明，每一个数需要参与莫队的数的个数是 $O(1)$ 级别的。这样的话复杂度降为 $n \sqrt n$ ，事实上我们可以把范围由 $\sqrt n$ 调整为 $100$ ~ $200$ 左右以获得一个较小的常数，跑到目前效率 rank 1。

最近准备学科营，平时考的模拟赛准备总结记录一下。这些题解会被分类到 Contest 目录下，可能只会讲笔者会的部分或笔者觉得有用的部分，思路可能会讲完整也可能不会，代码可能会放也可能不会，但题面和题意肯定是不会有的。大概就是这样（

Forest

考虑到每个节点出去只有一个父亲，所以要把修改都集中到自己和自己的父亲上去（而不是遍历自己的孩子）。为了方便维护，我们把原来的 $C_i$ 拆成

$$C_i = E_{a_i} + (B_i - D_i \times E_i + E_i + \sum E_{ P_j } [ j 是 i 的孩子])$$

通过简单的 trick 把括号内的东西（假设叫 $F_i$ ）放到 $i$ 节点上维护，可以使得 1 、 2 操作的复杂度变为 $O(1)$ ，但 3 操作需要遍历所有节点，复杂度是 $O(n)$ 。考虑优化，把每个节点都开个 multiset （或可删堆），用来存自己的每个孩子的 $F_i$ ，当自己的 $E_i$ 改变时利用自己的 multiset 去更新答案，同时当自己的 $F_i$ 改变时更新父亲的 multiset ，并利用父亲的 multiset 更新答案

Bear

20 分简单爆枚，40 分简单状压。100 分以对角线进行插头 dp ，还没写过。

Juice

考场上用一个乱搞做法 AC 了这题（也依赖与 IOI 赛制）。先枚举答案，对于每个答案进行 check ，方法如下。

先根据答案计算出分出的每个桶的大小 $S$，把给定的每个 $a_i$ 丢进 multiset 里。每次取出一个最小的 $A$，如果 $A > S$ ，那么就把 $A - S$ 丢回去；如果 $A < S$ ，那么就在 set.lower_bound(A) 到 –set.end() 的范围内随机一个迭代器配对。利用合适的随机种子和合适的调参，成功 Accepted。