题解 CF500G 【New Year Running】

JoshAlMan · 2020-10-08 21:54:45 · 题解

~~为了混积分把很久以前的题解搞上来~~

之前的题解是为了 T148321 这个搬完加了部分分的题写的，在这（部分分想法也可以在这里看），这里如果有逻辑递推混乱的可能是由于我拼起来的缘故。

这题的总体思路：即找两个循环序列的最小位置，使得他们的值相同。把公共的部分挖出来，发现对于每个循环序列都是连续的一段，然后通过树上的一些性质转化为 Exgcd 与同余不等式解决。

循环节长度

题目也有明确的提示，一个人按时刻顺序经过的编号是一个循环节，设 D 为循环节长度，u, v 是这条路径，d_{u, v} 是 u, v 的树上路径长度，那么：

D = 2d_{u,v}

所以，循环节长度是和 n 同阶的，对于每一个询问，走 g = \operatorname{lcm}(D_1, D_2) 次两者便都会重新走到起始位置。

一个暴力做法是把循环节序列找出来（可以暴力 dfs / 一个个跳 LCA，找都是 O(n) 的）然后，枚举答案最多只需要到 g 时刻，检查一下当前时刻走到的点是否相同就行了。时间复杂度 O(tn^2)。

一个部分分的想法

既然是一个循环节，我们尝试枚举两个路径都经过的点 x，尝试算出两个人相遇在 x 的最小时间，最后取最小值即可。

那么怎么算呢？

先考虑一个人。

在一次循环节中，有两个时刻 t_1 = d_{u, x}, t_2 = d_{u, v} + d_{v, x} 是在 x 的。

考虑 D 是循环节，所以说所有刚好在 x 的时刻可以表示为 xD + t_1 或 xD + t_2 的形式，其中 x 为非负整数。

对于另一个人同理，对于每一个人，我们找一个这样的数量关系 xD+T，其中 D, T 是固定的，x 是非负整数。

这样联立 xD_1 + T_1 = yD_2 + T_2 \Leftrightarrow xD_1 - yD_2 = T_2 - T_1，我们需要找到 x, y 都是非负整数解中，x 最小的那组（因为 x 固定 y 也就固定了，你让 y 最小也可），然后 xD_1 + T_1 就是答案。然后我们枚举四次（每个人两个时刻关系），一一求最小值就可以了。

问题即变成了求 ax - by = c 中 x, y 都为非负整数的解中，最小的 x。

用 exgcd 就可以了，先把 ax + by = c 的一组解求出来，然后令 b = -b, y = -y。

这样就有一组 ax - by = c 的解了，然后通解的形式就是 x =x + k \frac{b}{d},y = y + k\frac{a}{d}，这样先把 x, y 都调整到非负整数，然后再适量缩小就可以了。

时间复杂度 O(tn \log n)。

树上路径交

我们发现，两个树上路径的交（公共路径）也应该是一段连续的一条链（假设有两段，那么有环了）。

因此我们需要快速算出两个树上路径的子路径的两个端点。

你应该可以大型分类讨论，因为显然端点必须在其中两个点的 LCA 上。

还有一种很方便的找树上路径交的黑科技。

从 $lca(u, x), lca(u, y), lca(v, x),lca(v, y)$ 四个点找深度最大的两个点，记为 $p_1, p_2$。 * 若 $p_1 = p_2$ 且 $dep_{p1} < \max(dep_{lca(x, y)}, dep_{lca(u, v)})$ 那么无相交路径 * 否则相交路径就是 $p_1$ 到 $p_2

关于正确性，可以分类讨论每一种情况然后神奇的发现都满足......

分类讨论在公共路径相交的情况

设 u < v, x < y，那么这一段左端点 c_1 = \max(u, x) 右端点 c_2 = \min(v, y)，如果 c_1 > c_2 即无解。

若一样一个个点考虑发现时间复杂度太大，所以我们即考虑着整个一段。

设 X_1 为 x 第一次走到 c_1 的时间。

设 X_2 为 x 第一次走到 c_2 的时间。

设 U_1 为 u 第一次走到 c_1 的时间。

设 U_2 为 u 第一次走到 c_2 的时间。

这些都是 LCA 简单算一下距离就好了。

我们发现相遇无非两种情况：

两个人从同一侧出发，相遇。
两个人从两侧相向而行，相遇。

我们只需要两者取最优。

第一种情况

对于第一种情况，显然即向右走同时到 c_1，或向左走同时到 c_2 两种情况（若相遇到中间，那么上一个时刻肯定也是相同的点，与最小时间矛盾），这里用刚才那个 exgcd 的想法就行了。

第二种情况

对于第二种情况，我们枚举一个人第一次到一侧端点的时间 T_1，另一个人第一次到另一侧端点的时间 T_2，即 T_1 = U_1, T_2 = X_2 或 T_1 = U_2, T_2 = X_1 两种情况。

第一个人经过 c_1 的所有时间是 xD_1 + T_1，所以这个人在 (c_1, c_2) 这段上的时间就是一段区间： [xD_1 + T_1, xD_1 + T_1 + d_{c_1,c_2})].

对于另一个人，类似。

所以我们就要找到最小的 T，满足：

相遇在点上而不是边上
两个区间有交集

第一个条件

设答案为 T，假设相遇在 z 点，有：

T = xD_1 + T_1 + d(c_1, z)

T = yD_2 + T_2 + d(z, c_2)

两式相加再除以二：

T = \frac{xD_1 + yD_2+T_1+T_2+d_{c_1,c_2}}{2}

为了让 T 是整数，所以 xD_1 + yD_2+T_1+T_2+d_{c_1,c_2} 得是偶数，这个表达式前两项显然是偶数，所以只需要检查 T_1+T_2+d_{c_1,c_2} 是否是偶数就可以了，不是直接无解。

第二个条件

\max(xD_1 + T_1, yD_2 + T_2) \le T \le \min(xD_1 + T_1 + d_{c_1,c_2}, yD_2 + T_2 +d_{c_1,c_2})

这个满足等价于左右两边任意取出移项都满足不等关系。

拿出来列完后得到不等式等价于：

yD_2 + T_2 - T_1 - d_{c_1,c_2} \le xD_1 \le yD_2 + T_2 - T_1 + d_{c_1,c_2}

设 P = D_2, L = T_2 - T_1 - d_{c_1,c_2}, R = T_2 - T_1 + d_{c_1,c_2}, D = D_1，这些数都是常数。

我们要找到 yP + L \le xD \le yP + R，满足最小非负整数解 x，

这样为什么是对的呢，y 不也要最小吗？

把上面那个不等式等价对称一下：

xD_1 + T_1 - T_2 - d_{c_1,c_2} \le yD_2 \le xD_1 + T_1 - T_2 + d_{c_1,c_2}

因为当你 x 小，y 所在的区间也小，所以 x 肯定是得满足能找到 y 的情况下尽量小。

看上面那个不等式，显然 x 变小，y 也变小，且 R - L = 2d_{c_1,c_2} \le P。

若 R - L = 2d_{c_1,c_2} = P，这样子路径就是第二个人的路径下，此时让 x = 0 就可以满足（中间一定存在一个 P = D_2 的倍数）。
否则就是 R - L < P，这样的话这个区间内最多就只有一个满足条件的 y，所以那么算肯定是对的。

然后我们回归主题算最小的 x。

首先两个变量 P, D 你枚举复杂度肯定是不行的。

然后就想到转化为模意义下的不等式。

先把 L, D, R 都 \mod P。

特判 L > R 或 L = 0（中间一定存在一个 P = D_2 的倍数），那么让 x = 0，就可以满足这个式子。

特判后的 1 \le L \le R < P，由于 R - L < P，所以他们本身也是 P 的同一段下的，所以就是让这个式子在模意义下找到最小的也在那个区间里。

定义 P 的同一段：设 P, 2P, 3P, ...,nP 这些点为基准点，分成的若干段。

求解同余不等式.jpg

设 G(L, R, D, P) 为 yP + L \le xD \le yP + R，满足 1 \le L \le R < P, D < P，其中 x 的最小非负整数解。

这是一个模板题，题号是 POJ 3530，但肯定没多少人见过，这也算是一种类欧几里得算法吧。。

首先若 D = 0 那么显然就无解。。
否则假设 P = 0，这时候有解，就直接输出（此时肯定是最小值，若 P > 0，那么 x 的区间会变大）
否则 P > 0，由于上面找不到解（L, R 中间没有 D 的倍数），一定有 mD < L \le R < (m+1)D，这样我们就成功的把值域压到的 D 的同一段！移项有 xD - R \le yP \le xD -L，所以此时问题转化为了 G(-R \mod D, -L \mod D, P \mod D, D) 。这里可以模的基础也是，L, R 的区间限制压到了同一段，而 P 单点的模是没有影响的。

关于不等式两边可以取模的问题，国内没有较好的解释，基准点，同一段的想法也是我自己想出来的，若有理解不清 & 疏漏情况请评论）

复杂度分析可以关注最后两项，这跟 gcd 的复杂度是一样的，每次迭代 D 会变为原来的一半。

然后这个东西就是神奇的做到了 O(\log)，神奇到无与伦比。

时间复杂度 O((n + q) \log n)

#include <iostream>
#include <cstdio>

using namespace std;

typedef long long LL;

const int N = 200005, L = 18;
const LL INF = 9e18;

int n, q, dep[N], fa[N][L];

int head[N], numE = 0;

struct E{
    int next, v;
} e[N << 1];

void inline add(int u, int v) {
    e[++numE] = (E) { head[u], v };
    head[u] = numE; 
}

void dfs(int u) {
    for (int i = 1; i < L && fa[u][i - 1]; i++)
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    for (int i = head[u]; i; i = e[i].next) {
        int v = e[i].v;
        if (v == fa[u][0]) continue;
        fa[v][0] = u, dep[v] = dep[u] + 1;
        dfs(v);
    }
}

int inline lca(int x, int y) {
    if (dep[x] < dep[y]) swap(x, y);
    for (int i = L - 1; ~i; i--) 
        if (dep[x] - (1 << i) >= dep[y]) x = fa[x][i];
    if (x == y) return x;
    for (int i = L - 1; ~i; i--)
        if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
    return fa[x][0];
}

int inline d(int x, int y) {
    return dep[x] + dep[y] - 2 * dep[lca(x, y)];
}

LL exgcd(LL a, LL b, LL &x, LL &y) {
    if (b == 0) { x = 1, y = 0; return a; }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

LL inline work1(LL a, LL b, LL T1, LL T2) {
    LL x, y, c = T2 - T1, D1 = a; LL d = exgcd(a, b, x, y);
    if (c % d) return INF;
    x *= c / d, y *= -c / d;
    a /= d, b /= d;
    if (x < 0 || y < 0) {
        LL k = max((- x - 1) / b + 1, (- y - 1) / a + 1);
        x += k * b, y += k * a;
    }
    LL k = min(x / b, y / a); x -= k * b;
    return x * D1 + T1;
}

LL G(LL L, LL R, LL D, LL P) {
    if (!D || L > R) return INF;
    if (R / D * D >= L) return (L + D - 1) / D;
    LL x = G(((-R) % D + D) % D, ((-L) % D + D) % D, P % D, D);
    if (x == INF) return INF;
    return (x * P + L + D - 1) / D;
}

LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

LL work2(LL D1, LL D2, LL T1, LL T2, LL D) {
    if ((D + T1 + T2) & 1) return INF;
    LL L = ((T2 - T1 - D) % D2 + D2) % D2, R = ((T2 - T1 + D) % D2 + D2) % D2;
    LL x1 = 0;
    if (L && 2 * D < D2 && L <= R) x1 = G(L, R, D1 % D2, D2); 
    if (x1 == INF) return INF;
    LL x2 = (x1 * D1 + T1 - T2 + D) / D2;
    return (x1 * D1 + x2 * D2 + T1 + T2 + D) / 2;
}

LL inline query(int u, int v, int x, int y) {
    int p[4] = { lca(u, x), lca(u, y), lca(v, x), lca(v, y)};
    int w = lca(u, v), z = lca(x, y);
    int p1 = 0, p2 = 0;
    for (int i = 0; i < 4; i++)
        if (dep[p[i]] > dep[p1]) p2 = p1, p1 = p[i];
        else if (dep[p[i]] > dep[p2]) p2 = p[i];
    if (p1 == p2 && (dep[p1] < dep[w] || dep[p1] < dep[z])) return -1;
    // p1 - p2 是子路径
    int D1 = d(u, v) * 2, D2 = d(x, y) * 2, D = d(p1, p2);
    int U1 = d(u, p1), U2 = d(u, p2);
    if (U1 < U2) U2 = D1 - U2;
    else U1 = D1 - U1;
    int X1 = d(x, p1), X2 = d(x, p2);
    if (X1 < X2) X2 = D2 - X2;
    else X1 = D2 - X1;
    // U1：表示从 U1 出发，第一次踏上 p1 - p2 这条路径，并且起点是 p1 的时间。
    LL res = min(work1(D1, D2, U1, X1), work1(D1, D2, U2, X2));
    res = min(res, min(work2(D1, D2, U1, X2, D), work2(D1, D2, U2, X1, D)));
    return res == INF ? -1 : res;
}

int main() {
    scanf("%d", &n);
    for (int i = 1, u, v; i < n; i++)
        scanf("%d%d", &u, &v), add(u, v), add(v, u);
    dep[1] = 1, dfs(1);
    scanf("%d", &q);
    while (q--) {
        int u, v, x, y; scanf("%d%d%d%d", &u, &v, &x, &y);
        printf("%lld\n", query(u, v, x, y));
    }
    return 0;
}