黑科技就是处理一些问题的特殊技巧。

【1】两条路径在树上的交【from CF500G】

int depmax(int x, int y){return dep[x] > dep[y] ? x : y;}
int pathsection(int a, int b, int c, int d, int &e, int &f)
{
	int u = lca(a, b), v = lca(c, d);
	if(dep[u] > dep[v]) swap(a, c), swap(b, d), swap(u, v);
	if(lca(u, v) != u) return 0;
	
	e = depmax(lca(a, c), lca(a, d));
	f = depmax(lca(b, c), lca(b, d));
	if(max(dep[e], dep[f]) < dep[v]) return 0;
	e = depmax(e, v), f = depmax(f, v);
	return 1;
}

【2】处理\( L\le Dx \le R \) (\(Mod\) \(M\))下的最小自然数解【from CF500G】

LL G(LL M, LL D, LL L, LL R) // L <= Dx <= R (Mod M)
{
	if((L-1)/gcd(D,M) >= R/gcd(D,M)) return -1;
	if(D+D>M) return G(M, M-D, M-R, M-L);
	if((L-1)/D < R/D) return (L+D-1)/D;
	LL t=G(D, (D-M%D)%D, L%D, R%D);
	return (L+M*t+D-1)/D;
}