Visits: 244

CF704E Iron Man

题意

• 给定一棵 $n$ 个点的树。
• 有 $m$ 个人，第 $i$ 个人会在 $t_i$ 时刻出现在 $v_i$，并以每时刻 $c_i$ 条边的速度向 $u_i$ 移动，到达 $u_i$ 立刻消失。出现的时段是左闭右闭的，因此如果 $v_i = u_i$，则在 $t_i$ 时刻 $i$ 仍会出现。
• 求第一次有人相遇的时刻，或判断始终无人相遇。
• $n,m \le 10^5$，$t_i,c_i \le 10^4$。

题解

首先考虑一条链的情况。

暴力做法显然是对 $m$ 个人两两求答案然后取 $\min$，时间复杂度 $\mathcal O(m^2)$ 无法接受。

考虑用 multiset 按时间顺序维护所有人的相对位置，则只有在 multiset 中相邻的两个人有可能是答案。

时间复杂度 $\mathcal O(m \log m)$。

扩展到树上，将树进行树链剖分，则每个人被划分为 $\mathcal O(\log n)$ 条重链和轻链。

对每条链的答案求 $\min$ 即为最终答案，时间复杂度 $\mathcal O(n + m \log m \log n)$。

代码

struct frac {
    ll x, y;
    inline frac() {}
    inline frac(ll _x, ll _y = 1ll) : x(_x), y(_y) {
        ll g = __gcd(abs(x), abs(y));
        if (y < 0) g = -g;
        x /= g, y /= g;
    }
    inline friend frac operator + (frac e, frac b) { return frac(e.x * b.y + e.y * b.x, e.y * b.y); }
    inline friend frac operator - (frac e, frac b) { return frac(e.x * b.y - e.y * b.x, e.y * b.y); }
    inline friend frac operator * (frac e, frac b) { return frac(e.x * b.x, e.y * b.y); }
    inline friend frac operator / (frac e, frac b) { return frac(e.x * b.y, e.y * b.x); }
    inline friend bool operator < (frac e, frac b) { return e.x * b.y < b.x * e.y; }
    inline friend bool operator > (frac e, frac b) { return e.x * b.y > b.x * e.y; }
    inline friend bool operator <= (frac e, frac b) { return e.x * b.y <= b.x * e.y; }
    inline friend bool operator >= (frac e, frac b) { return e.x * b.y >= b.x * e.y; }
    inline friend bool operator == (frac e, frac b) { return e.x * b.y == b.x * e.y; }
};

const int N = 1e5 + 7, inf = 1e9;
int n, m, d[N], f[N], s[N], son[N], dfn[N], top[N], num;
vi e[N];
double Ans = inf;
frac tim, ans;
struct P {
    frac k, b, l, r;
    inline P() {}
    inline P(frac k, frac b, frac l, frac r) : k(k), b(b), l(l), r(r) {}
    inline friend bool operator < (P a, P b) {
        if (a.k * tim + a.b == b.k * tim + b.b)
            return a.l == b.l ? a.r == b.r ? a.k < b.k : a.r < b.r : a.l < b.l;
        return a.k * tim + a.b < b.k * tim + b.b;
    }
};
multiset<P> st;
vector<P> heavy[N], light[N];

inline int lca(int x, int y) {
    while (top[x] != top[y]) {
        if (d[top[x]] < d[top[y]]) swap(x, y);
        x = f[top[x]];
    }
    return d[x] < d[y] ? x : y;
}

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

void dfs(int x) {
    s[x] = 1;
    for (int y : e[x])
        if (y != f[x]) {
            f[y] = x, d[y] = d[x] + 1, dfs(y), s[x] += s[y];
            if (s[y] > s[son[x]]) son[x] = y;
        }
}

void dfs(int x, int p) {
    dfn[x] = ++num, top[x] = p;
    if (son[x]) dfs(son[x], p);
    for (int y : e[x])
        if (y != son[x] && y != f[x]) dfs(y, y);
}

inline void solve(int x, int y, frac s, frac v) {
    frac t = s + dist(x, y) / v;
    while (top[x] != top[y])
        if (d[top[x]] > d[top[y]]) {
            int p = top[x];
            heavy[p].pb(P(frac(0) - v, frac(d[x]) + v * s, s, s + frac(d[x] - d[p]) / v));
            s = s + frac(d[x] - d[p]) / v, x = top[x], p = f[x];
            light[x].pb(P(frac(0) - v, frac(d[x]) + v * s, s, s + frac(d[x] - d[p]) / v));
            s = s + frac(d[x] - d[p]) / v, x = f[x];
        } else {
            int p = top[y];
            heavy[p].pb(P(v, frac(d[y]) - v * t, t - frac(d[y] - d[p]) / v, t));
            t = t - frac(d[y] - d[p]) / v, y = top[y], p = f[y];
            light[y].pb(P(v, frac(d[y]) - v * t, t - frac(d[y] - d[p]) / v, t));
            t = t - frac(d[y] - d[p]) / v, y = f[y];
        }
    int p = top[x];
    if (d[x] > d[y]) heavy[p].pb(P(frac(0) - v, frac(d[x]) + v * s, s, t));
    else heavy[p].pb(P(v, frac(d[y]) - v * t, s, t));
}

inline frac get(P a, P b) {
    if (a.k == b.k) return a.b == b.b ? max(a.l, b.l) : frac(inf);
    frac o = (b.b - a.b) / (a.k - b.k);
    return o >= max(a.l, b.l) && o <= min(a.r, b.r) ? o : frac(inf);
}

inline void work(vector<P> p) {
    st.clear(), ans = frac(inf);
    vector<pair<P, bool>> q;
    for (P x : p) q.pb(mp(x, 1)), q.pb(mp(x, 0)); 
    sort(q.begin(), q.end(), [](pair<P, bool> x, pair<P, bool> y) {
        frac tx = x.se ? x.fi.l : x.fi.r, ty = y.se ? y.fi.l : y.fi.r;
        return tx == ty ? x.se > y.se : tx < ty;
    });
    for (auto x : q) {
        frac now = x.se ? x.fi.l : x.fi.r;
        if (now >= ans) break;
        tim = now;
        if (x.se) {
            auto tmp = st.insert(x.fi), pre = tmp, suf = tmp;
            if (pre != st.begin()) ans = min(ans, get(*--pre, *tmp));
            if (++suf != st.end()) ans = min(ans, get(*tmp, *suf));
        } else {
            auto tmp = st.lower_bound(x.fi), pre = tmp, suf = tmp;
            if (++suf != st.end() && pre != st.begin()) ans = min(ans, get(*--pre, *suf));
            st.erase(tmp);
        }
    }
    Ans = min(Ans, 1.0 * ans.x / ans.y);
}

int main() {
    rd(n), rd(m);
    for (int i = 1, x, y; i < n; i++) rd(x), rd(y), e[x].pb(y), e[y].pb(x);
    d[1] = 1, dfs(1), dfs(1, 1);
    for (int i = 1, t, c, x, y; i <= m; i++)
        rd(t), rd(c), rd(x), rd(y), solve(x, y, frac(t), frac(c));
    for (int i = 1; i <= n; i++) work(heavy[i]), work(light[i]);
    if (Ans == inf) return prints("-1"), 0;
    printf("%.10f\n", Ans);
    return 0;
}