记 d_i 表示 i 到根的路径异或和，则原条件转化为 a_x\oplus a_y\le d_x\oplus d_y\oplus a_{LCA(x,y)}。则容易想到枚举 LCA，统计不同子树之间点对的贡献。然而这样遍历的总次数没有保证，所以使用点分治，上式中 d 也变成点到分治中心的路径异或和。则问题转化为动态维护集合 S，集合元素为 (a,d) 二元组，多次询问 (a_x,d_x)，查询集合 S 中有多少 (a_y,d_y) 满足 a_x\oplus a_y\le d_x\oplus d_y\oplus a_{rt}。
发现只有令含 x 项和含 y 项分别在同侧，才能快速维护数量。但小于号没有交换律，所以先变不等号并移项，得到 a_x\oplus d_x\oplus a_{rt}\ne a_y\oplus d_y，然后按照 a\oplus d 分类后枚举 LCP 长度，分讨不同的最高位，最后加上相等的贡献即可。实现只需开一棵以 a\oplus d 为键值的 Trie 树，每个点记录子树内 a 该位为 0 或 1 的个数，可通过 a\oplus d 的情况得到 d 该位的值。查询时从根到对应叶子遍历一条链，处理链上节点的兄弟节点即可。
原题
点分治后的部分：P7502。
D2T1 跳跃树桩
题意
给出 n 个树桩，每个树桩有位置 x_i 和价值 a_i，从第一个树桩跳到第 n 个，要求在 x 时只能跳到 [x+L,x+R] 内的树桩，求最终经过树桩的价值降序排序后最大的字典序。n,a_i\le 5\times 10^5,x,L,R\le 10^9。
给定 n 个点 m 条边的有向无环图，起点为 1 号点。可以沿着有向边移动，也可以在任意时刻直接返回 1 号点。到达一个存在敌人的点时，需要消耗 a_i 点血量清除，清除后恢复 b_i 点血量，但整个过程中血量都不能低于 0。问最少需要多少初始血量才能清除所有敌人。n+m\le72,a_i,b_i\le 10^{15}。
题解
考虑如果没有任何顺序限制怎么做，此时若存在 i,j 两个点，则先取 i 需要的血量下限为 \max(a_i,a_i-b_i+a_j)，先取 j 需要的血量下限为 \max(a_j,a_j-b_j+a_i)，注意到这样可以确定任意两个之间的顺序，且比较有传递性，所以按照这样的顺序清除即可。
那么把这个放到树上怎么做？考虑排序后第一个点，那么一旦其父亲被清除，其一定会被马上清除，所以可以将其与父亲合并为一个点，新值为 a'=\max(a_f,a_f-b_f+a_x),b'=b_f-a_f+b_x-a_x+a'，这样和原来的两个点先后清除等价。原先两个点的所有儿子都接在这个新点上，直到最后只剩一个节点时其 a 值即为答案。
那 DAG 怎么做？注意到 n+m 很小，所以 n 比较小时直接 O(2^nn) 状压 DP 解决，大概能做 n\le24。那么剩余情况下 m\le48，这时搜索出所有可能的外向树，对每种树做一遍刚才树上的做法，复杂度为 O(cn\log n)，其中 c 为外向树方案数。考虑计算方案数的上界，此时 n\ge 24,\sum d_i=m\le 48,c=\prod d_i，其中 d 为某个点的入度。根据均值不等式，所有 d 均相等时 c 最大，也即 (\frac mn)^n，在最大的 n=24,m=48 时即为 2^{24}，总复杂度为 O(2^{\frac {n+m}3}n\log n)。
D2T3 括号序列
题意
给定 n,m,k,mod，求在 n 个盒子中各放一个长度不为 2k 的合法括号序列，总长为 2m 的方案数，对 mod 取模。n,m,k\le 10^7。
原题 + 题解
数据弱化版：AT_kupc2020_m，题解。
D3T1 简单函数
题意
给定 n 个数 x_i，需要支持单点修改，询问 i\in[1,n) 中是否存在 i 满足 f(x_i)f(x_{i+1})\le 0，其中 f(x)=(a\oplus x)-b，每次询问给出 a,b。若存在则输出任意一个，否则输出 -1。n,q\le 10^6,x,a,b<2^{30}。
题解
考虑如果 \max (a\oplus x)<b 或者 \min(a\oplus x)>b，则所有的 f(x) 均同号，无解。否则 min 和 max 的 f 值异号，考虑先找到这两个位置 l,r(l<r)，我们已知它们异号，则可以找到 mid=\frac{l+r}2，此时 l,r 中一定存在与 mid 异号的，所以判断一下即可把区间缩短到原来的一半，O(\log n) 次即可将区间缩小到 [i,i+1]，输出即可。
实现上需要求出 (a\oplus x) 的最值及其位置，所以对所有 x 建 Trie 树，在叶子节点上记录对应的所有下标即可，可以使用 set 或可删堆，也可以在外面单开一个 set 记录值和下标的对应关系。时间复杂度 O(q(\log V+\log n))。
考虑从 [1,n] 开始分治，每次只统计跨过 mid 的区间答案，然后分治到两边继续统计。分讨最大值位置，若最小值在同侧，则另一侧的长度有上界，直接将答案 r 累加上长度个数即可。若最小值在异侧，则另一侧的长度由于最大值在另一侧有上界，由于最小值在该侧有下界。这时枚举最大值侧的长度，相当于要在另一侧维护一个可重集 S，支持动态增删点，同时给出 x 后可以对于所有 y\in S，给 c_{\gcd(x,y)} 加上 1。
考虑设 c'_x 表示 x 为公因数出现了多少次，此时不一定是最小公因数，那么 c_x=c'_x-\sum_{y\mid x,y>x} c'_y，维护 c' 即可。考虑记数组 t_d 表示目前 S 中 d 的倍数个数，插入或删除时枚举因数更新 t，查询时枚举所有 x 的因数 d 给 c'_d 加上 t_d 即可。最后反演出 c 后累加给 r 即为答案。时间复杂度 O(nd(n)\log n)。
根据题意 f(a,b,i) 即为 ax+iy=b 中 x 的最小非负整数解，此时若 i>\max(a,b)，则 y=\frac{b-ax}i \le \frac bi<1，因此 y<0。所以可以设 z=-y，原式即 ax-iz=b,x=\frac {b+iz}a。此时使 x 取到最小非负整数的 z 需要满足 z 非负且 b+iz 整除 a，也即 iz\equiv -b\pmod a，根据定义得 z=f(i,-b,a)。
显然 f(p,q,r)=f(p\bmod r,q,r)，那么 \max(a,b) 及以下的直接暴力，\max(a,b) 以上的按对 a 取模的值分类，每一类的 z 相同，则为一个等差数列，计算一下左右端点累加即可。求 f 直接使用扩展欧几里得，时间复杂度 O(V\log V)，其中 V 为 a,b 的值域。
原题
Gym104053F。
2.17T1 删树
题意
给定一棵 n 个点的树，每次操作需要选择一部分点删去，要求操作后整棵树仍连通。对于 k\in[1,n]，求恰好 k 次将整棵树删空的方案数。n\le400。
题解
考虑在固定根节点，并且要求每个点不晚于其父亲被删时求解。那么我们设 t_u 表示 u 点被删去的轮数，要求即为 t_{u}\le t_{fa_u}。这样的 t 的方案数可以直接使用树形 DP + 前缀和优化求出。然而可能会出现某一轮没有节点被删的非法情况，需要容斥减去。这里设 r'_i 表示求出的方案数，那么 r_i=r'_i-\sum_{j=1}^{i-1} r_j\times {{i-1}\choose {j-1}}，也即要减去实际上只有 j 轮操作有点被删的方案数。
给定长为 n 的序列，q 次询问，每次给出 w 的初始值，之后依次遍历 i\in [1,n]，若 w\le a_i 可以选择给 w 异或上 a_i，求能异或上的数的最大个数。n\le2\times 10^5,q\le 10^6,a_i,w< 2^{30}。
题解
考虑找到 w 的最高位，那么其一定能异或掉所有最高位低于其的数，同时与其最高位相同的数最多只能异或一个。所以答案为 cnt 或 cnt+1，只需要对每个 w 判断是否存在与其最高位相同的 a_i 满足到 i 时 w\le a_i，且异或上 a_i 后还能把后面最高位低于 w 的数全都异或上。
容易想到先根据 w 的最高位分类，每一类分别判断。这时取出所有最高位低于 w 的 a_i，对其求前缀异或和 s_i，那么若有最高位与 w 相同的数 a_x，则满足 w\oplus s_{x-1}\ge a_x，且对于任意 j>x 都有 w\oplus a_x\oplus s_{j-1}\ge a_j 时 w 便存在对应的 a_x，可以让答案加 1。
观察发现后面的 O(n) 个限制有效的不多，因为从后往前非后缀最大值的限制一定可以删去，现在需要考虑相等情况。发现若存在 p,q 使得 a_p,a_q 均为后缀最大值，则 w 异或完 p 之前的元素后还需要异或上至少两个最高位与 a_p 相同的，此时若 w 高于 a_p 则后面一定都能取完，否则异或 a_p 后最高位下降，一定取不完。因此若出现两个相等的，直接将这两个限制保留并忽略之后的限制即可，这样总限制数为 O(\log V) 级别。
注意到每个限制均形如 w\oplus x\ge y，而枚举 LCP 长度即可证明满足限制的 w 在 Trie 树上为根深度不同的 \log V 棵子树，那么 O(\log V) 组 \log V 棵子树的交形成了 O(\log^2V) 棵子树，初始建出 w 的 Trie 树并在上面打标记即可，时间复杂度 O(n\log^2V) 或 O(n\log^3V)。
2.19T2 散步
题意
给定 n 个二元组 (a_i,b_i)，定义长为 n 的排列 p 权值为最小的 i\in [1,n] 使得 \forall j\ge i,\sum_{k=i}^j(a_{p_k}-b_{p_k})\ge0，且 \forall j<i,\sum_{k=i}^n(a_{p_k}-b_{p_k})+\sum_{k=1}^j(a_{p_k}-b_{p_k})\ge 0，若不存在则权值为 0。求所有 n! 种排列的权值之和。n\le 20。
题解
注意到 (a_i,b_i) 其实只会用到 s_i=a_i-b_i，题意中的限制其实相当于循环位移后的所有前缀和非负。此时若把 s_i 的前缀和放到坐标系中，则 i 对应的位置其实是最靠左的最低点。因为只有以最低点位移后的前缀和均非负，其中最小的 i 即为最靠左的。那么从最低点向左即为一段始终为正的折线，向右即为一段始终非负的折线。
所以需要求出 f_S,g_S 分别表示使用 S 中的 s_i 拼成始终为正或非负的折线方案数，枚举下一个选的段，判断合法并转移即可。这里需要注意 f 是反着向左始终为正，也即 s 的和始终为负。若设 U为全集，答案即为 \sum_S f_S\times g_{U-S}\times{\left|S\right|}。时间复杂度 O(n2^n)。
2.21T1 异或树
题意
给定一棵 n 个点的树，点有点权，分别求树上点两两之间路径按位与、按位或、按位异或值平方的和。n\le10^5,a_i< 2^{25}。