Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Archi is a small boy from Uzhlyandia. For Chef's birthday, he prepared a tree with $N$ vertices (numbered $1$ through $N$). Each edge in this tree has a certain length.

There are $M$ speedsters on the tree, numbered $1$ through $M$. For each valid $i$, speedster number $i$ starts at time $t_{i}$ from vertex number $u_{i}$ and runs straight to vertex number $v_{i}$ with constant velocity $s_{i}$. Before time $t_{i}$, the speedster is not considered to be present in the tree.

Chef is interested in the following question: for each vertex, what is the smallest time when a speedster is present at this vertex?

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
Each of the next $N-1$ lines contains three space-separated integers $u$, $v$ and $w$ denoting an edge between vertices $u$ and $v$ with length $w$.
The next line contains a single integer $M$.
For each valid $i$, the $i$-th of the next $M$ lines contains four space-separated integers $u_{i}$, $v_{i}$, $t_{i}$ and $s_{i}$ describing the $i$-th speedster.

------  Output ------
For each test case, print $N$ lines. For each valid $i$, the $i$-th of these lines should contain a single real number — the minimum time when the $i$-th vertex is visited by a speedster, or $-1$ if it is never visited. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$.

------  Constraints  ------
$1 ≤ T ≤ 100$
$1 ≤ N, M ≤ 2 \cdot 10^{5}$
$1 ≤ u, v ≤ N$
$1 ≤ w, t, s ≤ 10^{9}$
the graph described on the input is a tree
the sum of $N$ for all test cases does not exceed $2 \cdot 10^{5}$
the sum of $M$ for all test cases does not exceed $2 \cdot 10^{5}$

------  Subtasks ------
Subtask #1 (10 points):
the sum of $N$ for all test cases does not exceed $5 \cdot 10^{3}$
the sum of $M$ for all test cases does not exceed $5 \cdot 10^{3}$

Subtask #2 (20 points): the velocities of all speedsters are identical

Subtask #3 (20 points): the tree is a bamboo (a path)

Subtask #4 (50 points): original constraints

------  Example Input ------

1
5
1 2 3
1 3 5
3 4 1
4 5 4
3
2 1 3 4
4 2 1 3
1 3 2 6

------  Example Output ------

2.0000000
3.0000000
1.3333333
1.0000000
-1

Difficulty: VERY_HARD
Tags: Graph algorithms

Graph traversal

Geometry

Sweep line algorithms

Range queries

Segment trees revisited

Tree algorithms

Data structures

Tree queries
Skill types: Data structures

Range queries

Starter code:

Solutions:
import sys
sys.setrecursionlimit(10 ** 6)
T = int(input())
for _ in range(T):
	N = int(input())
	G = [[] for i in range(N)]
	for i in range(N - 1):
		(u, v, w) = map(int, input().split())
		G[u - 1].append((v - 1, w))
		G[v - 1].append((u - 1, w))
	lg = [0] * N
	li = [0] * N
	ld = [0] * N
	prv = [0] * N
	grp = []
	gprv = []
	gdep = []
	gdist = []

	def hld(v, p, d, gp, gi, gd):
		L = []
		D = []
		g = len(grp)
		grp.append(L)
		gdist.append(D)
		gprv.append((gp, gi, gd))
		gdep.append(d)
		di = i = 0
		while v is not None:
			lg[v] = g
			li[v] = i
			ld[v] = di
			D.append(di)
			L.append(v)
			nxt = None
			for (w, co) in G[v]:
				if w == p:
					continue
				if nxt is None:
					nxt = w
					di += co
				else:
					hld(w, v, d + 1, g, i, co)
			(p, v) = (v, nxt)
			i += 1
	hld(0, -1, 0, -1, -1, 0)

	def f(line, x):
		(r, p, q) = line
		if r == 1:
			return (x + q) / p
		return (-x + q) / p

	def _add_line(line, a, b, data, xs, k, l, r):
		if r <= a or b <= l:
			return
		m = (l + r) // 2
		if not (a <= l and r <= b):
			_add_line(line, a, b, data, xs, 2 * k + 1, l, m)
			_add_line(line, a, b, data, xs, 2 * k + 2, m, r)
			return
		if data[k] is None:
			data[k] = line
			return
		lx = xs[l]
		mx = xs[m]
		rx = xs[r - 1]
		(r0, p0, q0) = line
		(r1, p1, q1) = data[k]
		left = f(line, lx) < f(data[k], lx)
		mid = f(line, mx) < f(data[k], mx)
		right = f(line, rx) < f(data[k], rx)
		if left and right:
			data[k] = line
			return
		if not left and (not right):
			return
		if mid:
			(data[k], line) = (line, data[k])
		if left != mid:
			_add_line(line, a, b, data, xs, 2 * k + 1, l, m)
		else:
			_add_line(line, a, b, data, xs, 2 * k + 2, m, r)

	def add_line(line, a, b, i):
		return _add_line(line, a, b + 1, ldata[i], gdist[i], 0, 0, NN[i])

	def query(k, x, data, n):
		k += n - 1
		s = 1e+30
		while k >= 0:
			if data[k]:
				s = min(s, f(data[k], x))
			k = (k - 1) // 2
		return s
	LL = len(grp)
	NN = [2 ** (len(e) - 1).bit_length() for e in grp]
	ldata = [[None] * (2 * n + 1) for n in NN]
	M = int(input())
	for i in range(M):
		(u, v, t, s) = map(int, input().split())
		u -= 1
		v -= 1
		ug = lg[u]
		vg = lg[v]
		if lg[u] == lg[v]:
			ui = li[u]
			vi = li[v]
			ud = ld[u]
			vd = ld[v]
			if ui <= vi:
				add_line((1, s, t * s - ud), ui, vi, ug)
			else:
				add_line((-1, s, t * s + ud), vi, ui, ug)
		else:
			udp = gdep[ug]
			vdp = gdep[vg]
			ud = ld[u]
			ui = li[u]
			d = 0
			while udp > vdp:
				ud = gdist[ug][ui]
				d += ud
				add_line((-1, s, t * s + d), 0, ui, ug)
				(ug, ui, ud) = gprv[ug]
				d += ud
				udp -= 1
			st = []
			vd = ld[v]
			vi = li[v]
			while udp < vdp:
				vd = gdist[vg][vi]
				st.append((vd, vg, vi))
				(vg, vi, vd) = gprv[vg]
				vdp -= 1
			while ug != vg:
				ud = gdist[ug][ui]
				d += ud
				add_line((-1, s, t * s + d), 0, ui, ug)
				(ug, ui, ud) = gprv[ug]
				d += ud
				udp -= 1
				vd = gdist[vg][vi]
				st.append((vd, vg, vi))
				(vg, vi, vd) = gprv[vg]
				vdp -= 1
			ud = gdist[ug][ui]
			vd = gdist[vg][vi]
			if ui <= vi:
				add_line((1, s, t * s + (d - ud)), ui, vi, ug)
			else:
				add_line((-1, s, t * s + (d + ud)), vi, ui, ug)
			d += abs(ud - vd)
			while st:
				(e, vg, vi) = st.pop()
				vd = gprv[vg][2]
				d += vd
				add_line((1, s, t * s + d), 0, vi, vg)
				d += e
	ans = []
	for i in range(N):
		g = lg[i]
		j = li[i]
		d = ld[i]
		y = query(j, d, ldata[g], NN[g])
		if y >= 1e+29:
			ans.append('-1')
		else:
			ans.append('%.08f' % y)
	print(*ans, sep='\n')