• T1

考虑哪个节点更深。

那么每次 $(x+q-2)/q$ 得到它的父亲节点。

暴力 $lca$ 即可，特判 $q=1$ 。

• T2

对于不重集合 每个元素只有选与不选两种情况。

输出 $2^{unique(a)}-2$ 即可。

• T3

按照题意，每次把正方形分成均等的四份即可，不难发现每次分开的正方形都是 $2^i+1$ 的，按照题意模拟即可。

• T4

对于 $20\% pts$ 的数据，枚举子集即可。

对于 $n\le 2000$ 每次枚举目标 $gcd=d$

那么就能得出不同数字的具体贡献。 是因子的就是 $d$ 否则是 $-x$。

对于这个序列之间跑 最大子段和即可。

对于 $x=0$ 预处理每个数的因数，每次枚举 $gcd=d$

求出 $max\{d\times cnt\}$ 就是答案。

对于全部的数据范围，考虑每个数的因子个数最多只有$2\sqrt{n}$ 个，维护每个因子出现的位置在哪里，压缩序列为 $d,-x\times l_i,d,...$ 再跑最大子序列就是目标答案了。

时间复杂度 $O(n\sqrt{V})$ ， $V$表示值域