题解 CF704E 【Iron Man】

> [CF704E Iron Man](https://codeforces.com/contest/704/problem/E) ## 题意 - 给定一棵 $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)$。 ## 代码 ```cpp 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; } ```