AGC009D Uninity
如果构造一棵点分树，答案是 \(\log n\)，这是答案上界。
将问题转化为每次将若干棵 Uninity 为 \(k\) 的树连接到一个点上时将点打上 \(k+1\) 的 \(tag\)。
看题面有一个很显然的结论就是两个 \(tag=k\) 的点间的路径上一定有一个 \(tag>k\)。考虑记录 \(f_u\) 表示 \(u\) 的子树内 存在 且 还没有找到比它大的 的 \(tag\) 值的集合。
那么对于一个点 \(u\) 要满足：
- \(\forall v\in child(u),tag_u\notin f_v\)
- \(\forall v1,v2\in child(u)\) 且 \(v1\ne v2,tag_u>max(f_{v1}\cap f_{v2})\)
每次 \(tag\) 取可行的最小值。
ARC077F SS
设 \(T\) 为 \(S\) 减去 \(S\) 的最长 border 后缀得到的字符串。
如果 \(|T|\) 为 \(|S|\) 的约数，意味着 \(S\) 是一个循环串，循环节为 \(T\)。所以变化是这样的：
\[\texttt{SS}\rightarrow\texttt{STST}\rightarrow\texttt{STTSTT}\rightarrow\texttt{STTTSTTT}
\]
操作次数很多，只有前半部分有用，相当于：
\[\texttt{S}\rightarrow\texttt{ST}\rightarrow\texttt{STT}\rightarrow\texttt{STTT}
\]
差分求解。
如果 \(|T|\) 不是 \(|S|\) 的约数，那么就是普通情况，变化长这样：
\[\texttt{SS}\rightarrow\texttt{STST}\rightarrow\texttt{STSSTS}\rightarrow\texttt{STSSTSTSST}
\]
还是只看前半部分：
\[\texttt{S}\rightarrow\texttt{ST}\rightarrow\texttt{STS}\rightarrow\texttt{STSST}
\]
发现 \(s_i=s_{i-1}+s_{i-2}\) 长度指数级增长，暴力求就可以。
ARC136E Non-coprime DAG
质数太多，不好处理，考虑用 \(2\) 作为桥梁分析限制条件。
考虑两个点 \(i,j\)，\(i<j\)。
设 \(p(x)\) 表示 \(x\) 的最小质因子。
| \(i\) | \(j\) | 可达条件 |
|---|---|---|
| 奇 | 奇 | \(i+p(i)\le j-p(j)\) |
| 奇 | 偶 | \(i+p(i)\le j\) |
| 偶 | 奇 | \(i\le j-p(j)\) |
| 偶 | 偶 | \(true\) |
显然最多只能取一个偶数。
如果取了偶数 \(x\)，则取 \(i<x,i+p(i)>x\) 或 \(i>x,i-p(i)<x\)。
如果全部取奇数，则须满足 \(\min\{i+p(i)\}>\max\{i-p(i)\}\)。
CF297C Splitting the Uniqueness
认真读题会发现一个很有用的条件就是 \(s\) 互不相同。