$Link$

有 $n$ 棵竹子，每棵有一个初始高度 $h_i$ 和生长速度 $a_i$，每天 $n$ 棵竹子都会分别生长 $a_i$ 高度。

你可以把某一棵竹子砍下 $p$ 高度（如果竹子高度不足 $p$ 则砍到 $0$），这个操作每天可以最多做 $k$ 次。

问 $m$ 天后，最高的竹子的高度的最小值。

$1\le n\le10^5,1\le m\le5000,1\le k\le 10,1\le h_i,a_i\le10^9$。

$Link$

给你一棵 $n$ 个点的树，定义每个点的权值为其到最远的叶子节点的距离 $dis$。

$q$ 次询问，每次询问给你一个 $l$，问最多能选出多少个点，使得 $dis_{max}-dis_{min}\le l$，且这些点联通。

$1\le n\le10^5,1\le q\le50$。

写在前面

刚刚结束省夏，又来 $APIO$。

话说这回因为疫情只能线上比，规则居然写可以上网查阅资料，代码是自己写的就行？？？

什么鬼操作。

简介

$ Manacher $ ，俗称马拉车，是一种可以在 $ O(n) $ 的时间复杂度下，求出一个字符串的所有回文子串的神奇算法。

$Link$

给你一个 $n$ 个点的树，根为 $1$ 号点。

共有 $m$ 次询问，每次询问给你 $k$ 个数，问能否找到其中一个数，使得其他点在从根到这个数的路径上或与其距离为 $1$。

$ 2\le n\le 2\times 10^5,1\le m\le 2\times 10^5,\sum k\le 2\times 10^5$。

$Link$

$n$ 个点围成一圈，每个点都有类型。

给每个点染色，要求相邻的不同类型的点不能染同种颜色。

求最少颜色数和染色方案。

共有 $t$ 组数据。

$1\le t\le 10^4,3\le n\le 2\times 10^5,\sum n\le 2\times 10^5$。

$Link$

给你一个 $n$ 的排列 $p$，以及排列中每个数的颜色 $c$。

定义若 $c=a\times b$，则 $c_i=b_{a_i}$。

找到最小的正整数 $k$ 使得将 $p$ 变为 $p^k$ 后，存在一个 $i$ 使得 $c_i=c_{p_i}=c_{p_{p_i}}=\cdots$。

共有 $t$ 组数据。

$1\le t\le 10^4,\sum n\le 2\times 10^5$。

$Link$

定义一个数中，连续 $k$ 个数相等，为一个长度为 $k$ 的块。

要求块外两端的数字不同于块内数字。

写下从 $0\dots 10^n-1$ 的所有数，不足 $n$ 位的用前导 $0$ 补足。

对于每一个 $i=1\dots n$ 求这些数中有多少长度为 $i$ 的块。

$n\le 2\times 10^5$，答案对 $998244353$ 取模。

定义

将一个字符串的每个后缀按字典序排序，后缀数组 $ sa_i $ 表示排名为 $ i $ 的后缀的起始下标。