树上路径问题首选点分治，然后二分最后最小的距离
考虑经过当前分治重心的路径，记录子树里面的点到它的距离和它属于哪个子树
然后按照距离排序
对于当前的二分距离 \(lim\) ，扫所有点分树上的点对，考虑合法的区间长度是单调的，也就是 \(l\) 在不断增加的过程中 \(r\) 是减小的
在单调指针移动的过程中记录有多少的点属于哪个子树，然后对于当前的点计算答案的时候减掉即可
值得指出的是，实现的时候右边的指针也可能往右移，桶跟着更新就行
优化暴力题
维护区间的 \(and,or\) 和，以 \(and\) 为例，当前的区间如果 \(and\) 和和修改权值 \(and\) 完了不变，那么就直接返回
反之递归
复杂度考虑按照普通的势能线段树进行分析即可
这题加深了对行列式的值和排列的关系的认识
感觉就和做的把边看成 \([x^1]\) 然后求长度为 \(L\) 的路径长度是 \([x^L]\) 前面的系数一样好
考虑行列式求值的公式，考虑把 \(-1\) 的位置视为 \(0\)，那么有这个点的排列对于行列式值得贡献为 \(0\)
如果说有一种手段使得让其满足排列的贡献最后能消掉，或者 \(\bmod\) 意义下为 \(1\) ,就说明有解
剩下的部分是一个构造，熟练的话可以直接切掉
设素数 \(P\) 满足 \(P\equiv 1 \mod k\)，\(g\) 表示 \(\mod P\) 意义下的 \(k\) 次单位根
求出来原根之后 ksm(root,(mod-1)/k) 就能得到
那么把原来的矩阵中 \(-1\) 的位置设为 \(0\) ，有 \(val\) 的位置设成 rand()*ksm(x,a[i][j])
把 \(x=g^{1\dots n}\) 带入求行列式的值即可
其实理解很简单，因为是行列式求值，对于一个排列，有 \(-1\) 的贡献为 \(0\)
没有 \(-1\) 的那些，只有和是 \(k\) 的倍数的排列，其贡献是非零的
原文：https://www.cnblogs.com/yspm/p/14529979.html