Description

Given a tree $T$ with $n$ vertices labeled $0\sim n-1$, each edge has a weight $w_i$.

There are $q$ queries $(p, v_p, t, v_t)$, answer the following question:

• A policeman and a thief start from vertices $p$ and $t$ simultaneously, with maximum speeds $v_p$ and $v_t$ respectively.
• Assuming both parties know each other's situation and adopt optimal strategies, find the time when the thief is caught, expressed as a fraction.

Limitations

$2\le n\le 10^5$

$1\le q\le 10^5$

$0\le p,t\le n-1$

$1\le w_i,v_p,v_t\le 10^6$

Time Limit : $2\text{s}$

Memory Limit : $1024\text{MB}$

Solution

First, root the tree at an arbitrary vertex. Consider a query. Let $d_u$ denote the farthest distance the thief can escape from vertex $u$ (obviously not moving toward the policeman).

If $v_t \ge v_p$, the policeman cannot catch up. Let $u$ be the first vertex on the path $t \to p$ that the policeman can reach before the thief. The thief will go to $u$ and then escape as far as possible. The time is $\frac{d_u + \text{dist}(u, p)}{v_p}$.

If $v_t < v_p$, the policeman can chase. There are two strategies. Let $u$ be the last vertex on the path $p \to t$ where it is not faster to chase further. Then there are two cases:

• The thief goes to $u$ and then escapes directly, same formula as above.
• The thief is caught at a neighbor $v$ of $u$, with time $\frac{\text{dist}(v, p) - \text{dist}(v, t)}{v_p - v_t}$. Considering the chasing direction, if $p$ is in the subtree of $u$, then obviously chase into that subtree; otherwise chase toward the parent.

Clearly, the vertex $u$ satisfying the condition on the path is monotonic. To find $u$, we can binary search directly on the path. A convenient implementation is to first check whether the LCA satisfies the condition, then jump up from one side using binary lifting.

We also need to compute $d_u$. Before processing queries, use a rerooting DP to calculate the longest/second longest chains from $u$ downward/upward, then handle cases based on the relative positions of $p$ and $u$.

Time & Space complexity: $O(n \log n)$.