AGC005

A STring

不会，有没有老鸽蕉蕉我/kk/kel/dk

单调栈板子题

先得出直径(d=max a)，然后所有(agefrac d2)，且至少要有一条直径

还有正好取到最小值(agefrac d2)的点数有限制

容斥，设(f_i)表示取了(i)个不合法的方案数，答案是(sum f_i(n-i)!)

建一个图，每个点拆成(i_L,i_R)如果选了这个点表示(i)取到了不合法且占据了位置(i-K/i+K)

连边(i_L,i_R)和(i_R,(i+2K)_L)，限制变成了要选一个独立集

然后这个图可以拆成若干条链，一条长为(L)的链选(x)个不相邻的点方案数是(inom{L-x+1}{x})

定义红树上的边长为这条边端点在蓝树上的距离

如果有一条红树上的边长(ge 3)那么只要(A)走到了这条边一个端点而且没暴毙那么可以一直玩B，答案无限

否则从蓝树上看，(A)肯定走不出(B)所在的子树，不如去一个很深的地方等死

在两棵树上搜两遍就好了

对每个点单独计算贡献，对点(x)计算大小为(i)的连通块会包含(x)的方案数

但是不好算，改为算大小为(i)的连通块不会包含(x)的方案数

然后这个东西就是用(x)作为根，拿出子树的siz数组，就是(suminom{siz}{i})

显然可以ntt优化= =