因为没有模拟赛，所以考虑捡捡之前漏下的小点。
注：LCA 之后的讲解中可能会出现一些自由的文字，酌情阅读。
dfs 序求 LCA
倍增 LCA 的常数还是过于大了，虽然好记但会导致我们在一些数据奇异的题中比其它方式求 LCA 的人的得分要低。
所以就有了这个用 dfs 序求 lca 的高科技，在时间效率和代码好写程度上都薄纱其它方法的狠活。
思路
建议画个简单图手模一下
设我们要求 \(u\)，\(v\) 两点的 lca 为 \(d\)，两点不重合，令 \(dfn_u\lt dfn_v\)。
首先考虑 \(u\)，\(v\) 之间不存在祖先关系的情况。此时 dfs 的顺序是从 \(d\) 到 \(u\) 再回退到 \(d\) 再到 \(v\)。那么根据 dfs 的性质，任何 \(d\) 及其祖先的点均不会出现在 \(dfn_u\) 到 \(dfn_v\) 这个范围内；再考虑 \(d\) 在 \(v\) 方向的第一个子节点 \(x\)，显然有 \(dfn_u\lt dfn_x\lt dfn_v\)。也就是说，我们只需要找出一个 dfs 序在上述范围内的深度最浅的点，其父节点就是我们所求的 \(d\)。
再考虑二者存在祖先关系怎么处理。暴力判断虽然可行，但与我们这样做的目的就相悖了，我们要找到一个优雅的方式来求解。由 \(dfn_u\lt dfn_v\) 可知 \(u\) 为 \(v\) 祖先，我们按上述方法寻找到的 \(x\) 为 \(u\)，显然与答案不符。所以我们考虑修改上述范围，将其改成 \(dfn_u+1\) ~\(dfn_v\) 即可。思考这样做在情况一的正确性，由于 \(u\) 显然不能成为我们要找的 \(x\)，所以去掉该点不会对答案造成影响。
唯一的不足就是无法处理 \(u=v\) 的情况，特判一下即可。
实现
借助 ST 表来完成，预处理的复杂度是 \(\mathcal{O(n\log n)}\) 的，但常数小了很多。
模板题代码：
const int Ratio = 0;
const int N = 5e5 + 5;
int n, m, s;
namespace WLCA
{
int dfn[N], tot, st[31][N], lg[N];
int hh[N], to[N << 1], ne[N << 1], cnt;
void Wadd(int u, int v){to[++cnt] = v, ne[cnt] = hh[u], hh[u] = cnt;}
int Wget(int x, int y){return dfn[x] < dfn[y] ? x : y;}
void Wdfs(int u, int fa)
{
dfn[u] = ++tot, st[0][dfn[u]] = fa;
for(int i = hh[u]; i != -1; i = ne[i])
{
int v = to[i];
if(v == fa) continue;
Wdfs(v, u);
}
}
int Wlca(int x, int y)
{
if(x == y) return x;
if((x = dfn[x]) > (y = dfn[y])) swap(x, y);
int d = lg[y - x++];
return Wget(st[d][x], st[d][y - (1 << d) + 1]);
}
short main()
{
n = qr, m = qr, s = qr;
memset(hh, -1, sizeof hh);
for(int i = 1; i < n; i++)
{
int a = qr, b = qr;
Wadd(a, b), Wadd(b, a);
}
Wdfs(s, 0);
for(int i = 2; i <= tot + 1; i++)
lg[i] = lg[i >> 1] + 1;
for(int i = 1; i <= lg[n]; i++)
for(int j = 1; j + (1 << i) - 1 <= n; j++)
st[i][j] = Wget(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]);
for(int i = 1; i <= m; i++)
{
int a = qr, b = qr;
printf("%d\n", Wlca(a, b));
}
return Ratio;
}
}
- 顶针教的，讲的比较好的是这篇博客，引用了部分内容。
建虚树
众所周知，点有五个，关键点有三个。
你说的不对，但是虚树有两种建法，一种是好写好理解复杂度不好的双 sort 建树，一种是不好写不好理解复杂度好的单调栈维护。但是题解不会顺着你的思路来，所以两种方法都要深度理解下。
双 sort 建树
思路
好理解，不写了。
其实理解它主要依赖于理解虚树到底要留哪些点。知道为什么留 lca 了就明白为什么这么建树了。
实现很简单，按 dfs 序 sort 一遍，开随便什么存一下每个点及相邻点的 lca，再 sort 一遍，再 unique 一遍，然后根据原树上关系加边就行了。
实现
好写，不写了。
int dfn[N], tot, a[N], b[N], m, len;
bool cmp(int a, int b){return dfn[a] < dfn[b];}
void Wbuild()
{
sort(a + 1, a + m + 1, cmp);
for(int i = 1; i < m; i++)
b[++len] = a[i], b[++len] = Wlca(a[i], a[i + 1]);
b[++len] = a[m];
sort(b + 1, b + len + 1, cmp);
len = unique(b + 1, b + len + 1) - b - 1;
for(int i = 1; i < len; i++)
{
int lca = Wlca(b[i], b[i + 1]);
Wadd(lca, b[i + 1]);
}
}
单调栈建树
5k：为什么要学单调栈建树？
Ratio：不是说这个跑得快点
5k：复杂度都是一样的，少的这点常数也不会去卡，再说了单调栈你还容易写挂，双 sort 就很难写挂
所以不写这个了。
差分约束
由于昨天晚上饭堂，导致写 D 时被迫复习了差分约束。
经过
具体的，开始先打了一遍本来能过的 dfs 做法，然后由于我觉得可能会爆 1e18 就很天才的给 i 赋了一个 \(\frac{max+min}{2}\)，然后其它还有很多脑瘫的地方所以 WA + TLE 导致我觉得这种做法不可行然后怒吃 8 发罚时。
差分约束系统 是一种特殊的 \(n\) 元一次方程组，它包含……
嗯，这有啥好说的，还是挑重点吧。
给你若干个形如 \(x_i + x_j \le k\) 的限制，询问是否有符合上述所有限制的解。
思路
联想大法好：发现 \(x_i - x_j \le k\) 和求醉短路中的松弛操作 \(dis_v\lt dis_u +w_i\) 很像，因此我们将每一个数 \(x_i\) 都当做图中的一个点，每个约束看作由 \(x_j\) 向 \(x_i\) 引一条长度为 \(k\) 的边。
如果符号是 \(\gt\) 你就两边同时乘上一个 \(-1\)，如果是 \(=\) 你就看成两个限制 \(x_i-x_j\le k\)，\(x_j-x_i\le -k\)，连两条边就行了。至于其它的符号，本质上没啥区别，自己转化一下。
实现
公元 4202 年，智慧的人类掌握了复活已死的事物这一技术，并以 SPFA 为对象进行了秘密测试，结果未知。
采用 SPFA 算法，若跑出负环了显然是无解的情况，否则跑出的 \(dis_i\) 就是所有限制下的一组解。
由于限制是以差分形式存在的，所以若 \(a_1,a_2\cdots a_n\) 是符合题目要求的一组解，那么 \(a_1 + k,a_2+k\cdots a_n+k\) 也是符合要求的另一组解。由这个性质可以实现一些题目中对解的范围限制。
例题：无
啊不对，昨天晚上刚做了一道。
例题：有
谔谔虽然你们暴力都过了并且我的暴力改完也过了，但我赛时打的差分约束所以它就是模板题。
很好的条件，确保了一定有解，所以我们完全可以省掉判负环的步骤，直接开局建一个超级原点，按差分的性质连边，跑一遍就没了，因为 \(10^9\times 2\times 10^5\lt 10^{18}\)，所以压根不用管题目的 \(x_i\le |10^{18}|\)，初始值设成 0 肯定跑不炸。
Submitted code 这里放的现打的因为赛时太唐了做了一堆唐氏操作，喜欢唐人的可以自己去搜。
鲜花
-
1 能不能不要再逆天发言了，哦好像这几个字排列已经被你们发掘完了，怪不得没动静了
-
2
Ratio：jijidawang 你想说点什么吗
jijidawang：我想说点什么吗
完结撒花~
