首先考虑 (a,b,c) 合法的条件是什么，m 位以上的必定要全相等，如果第 m 位也全相等就直接合法了。否则不妨设 b,c 在第 m 位相等，且 a 在第 m 位与它们不同，那么只需要满足 a\oplus c\le k,a\oplus b\le k 即可，也就是说，如果我们枚举所有被包含的化学品，就可以在 O(k\log k) 的时间复杂度内解决这一部分。
如果有一个子树代表的前缀最低位比 m 位还高，那么如果选了这棵子树内的一个点，其它两个点也必定在这棵子树内，并且可以发现每棵子树的贡献仅与其代表前缀最低位有关，这一部分易于统计。下面认为剩余子树都不满足这个条件。
先考虑第 m 位全相等的情况，考虑枚举所有的代表前缀最低位为第 m 位的子树，这一子树内任取三个点均满足这种情况，且不会漏数，由于上一段解决了更高位的问题，这里的复杂度为 O(n\log V)。
在解决下一部分之前，先观察一下对于某个 x，满足 x\oplus y\le k 的 y 的形态，其可以表示为，在 trie 上从根到 x\oplus k 的路径上，如果 k 的某位是 1，那么在路径上对应位置伸出一棵子树，这些子树内的点就是所有的 y。
那么对于一棵子树内的所有 x（设这棵子树代表的前缀为 s，最低位为 d），y 的形态大致为首先先从根到 s\oplus k 的第 d 位并进行统计，后面每次从左右儿子中随机选择一个向下走，由 k 的当前位决定是否将另一个儿子包含的子树大小加入。
对于不全相等的情况，我们枚举所有区间形成的那 O(n\log V) 个子树 s。对于 s 中的所有数 x，满足 x\oplus y\le k 且 x,y 的 m 位不同的 y 个数设为 cnt，要求的即为 \sum\binom{cnt}{2}，只需要维护 \sum cnt^2,\sum cnt 即可。
考虑 dp，对于某个 trie 上的点 x，设 dp_{x,i(0/1/2)} 表示在 x 子树内，随机选择左右儿子向下走，并仅加入位数比 x 代表前缀最低位还低且 k 对应位为 1 的那些子树，得到的值的 i 次方和，这个 dp 是可以展开平方式转移的。
对于枚举到的每个 s，在其 \oplus k 后得到的对应子树 t 上用其 dp 值进行计算，可以在 O(n\log^2 V) 或 O(n\log V) 的时间复杂度内做完整个问题。