Ishank lives in a country in which there are N$N$ cities and N−1$N-1$ roads. All the cities are connected via these roads. Each city has been assigned a unique number from 1 to N$N$. The country can be assumed as a tree, with nodes representing the cities and edges representing the roads. The tree is rooted at 1.Every Time, when a traveler through a road, he will either gain some amount or has to pay some amount.
Abhineet is a traveler and wishes to travel to various cities in this country. There's a law in the country for travelers, according to which, when a traveler moves from the city A$A$ to city B$B$, where city A$A$ and B$B$ are connected by a road then the traveler is either paid or has to pay the amount of money equal to profit or loss respectively. When he moves from A$A$ to B$B$, he hires a special kind of vehicle which can reverse its direction at most once. Reversing the direction means earlier the vehicle is going towards the root, then away from the root or vice versa. Abhineet is analyzing his trip and therefore gave Q$Q$ queries to his friend, Ishank, a great coder. In every query, he gives two cities A$A$ and B$B$. Ishank has to calculate the maximum amount he can gain (if he cannot gain, then the minimum amount he will lose) if he goes from the city A$A$ to city B$B$.

-----Input:-----
-The first line of the input contains a two space-separated integers N and Q.
-The next N-1 line contains 3 space-separated integers Xi and Yi and Zi denoting that cities Xi and Yi are connected by a road which gives profit Zi (Negative Zi represents loss).
-The next Q contains 2 space-separated integers A and B denoting two cities.

-----Output:-----
Print a single line corresponding to each query — the maximum amount he can gain (if he cannot gain, then the minimum amount he will lose with negative sign) if he goes from city A to city B.

-----Constraints-----
- 2≤N≤105$2 \leq N \leq 10^5$
- 1≤Q≤105$1 \leq Q \leq 10^5$
- 1≤Xi,Yi,A,B≤N$1 \leq Xi, Yi, A, B \leq N$
- abs(Zi)≤109$ abs(Zi) \leq 10^9$

-----Sample Input:-----
9 5
1 2 8
1 3 -9
2 4 1
2 5 -6
3 6 7
3 7 6
6 8 3
6 9 4
1 2
2 7
4 3
3 2
8 9

-----Sample Output:-----
10
5
0
-1
21

-----EXPLANATION:-----
In the first query, he goes from 1 to 2, 2 to 4, takes a turn and go to 2. Therefore profit=8+1+1=10.

Difficulty: VERY_HARD
Tags: Graph algorithms

Tree queries

Starter code:

Solutions:
try:
	X = list(map(int, input().split()))
except:
	X = [0, 0]
ch = []
chnew = []
par = {}
par[1] = 0
for i in range(X[0] + 1):
	ch.append([])
	chnew.append([])
for i in range(X[0] - 1):
	Y = list(map(int, input().split()))
	ch[Y[0]].append([Y[1], Y[2]])
	ch[Y[1]].append([Y[0], Y[2]])
tre = [1]
while len(tre):
	cr = tre[-1]
	tre = tre[:-1]
	for i in ch[cr]:
		chnew[cr].append(i)
		par[i[0]] = [cr, i[1]]
		tre.append(i[0])
		for j in ch[i[0]]:
			if j[0] == cr:
				ch[i[0]].remove(j)
				break
ch = chnew

def goup(par, nd):
	if nd == 1:
		return 0
	else:
		p = par[nd]
		ans = p[1] + goup(par, p[0])
		return max([ans, 0])

def godown(ch, nd):
	ans = 0
	for i in ch[nd]:
		ans = max([i[1] + godown(ch, i[0]), ans])
	return ans
for i in range(X[1]):
	Z = list(map(int, input().split()))
	r = Z[0]
	s = Z[1]
	nans = 0
	while r != s:
		if r > s:
			nans = nans + par[r][1]
			r = par[r][0]
		else:
			nans = nans + par[s][1]
			s = par[s][0]
	if r == Z[0] or r == Z[1]:
		if Z[0] < Z[1]:
			nans = nans + 2 * max(goup(par, Z[0]), godown(ch, Z[1]))
		else:
			nans = nans + 2 * max(goup(par, Z[1]), godown(ch, Z[0]))
	else:
		nans = nans + 2 * goup(par, r)
	print(nans)


def up(dp, nod):
	if nod == 1:
		return 0
	else:
		p = dp[nod]
		ans = p[1] + up(dp, p[0])
		return max([ans, 0])

def down(city, nod):
	ans = 0
	for i in city[nod]:
		ans = max([i[1] + down(city, i[0]), ans])
	return ans
try:
	(n, q) = map(int, input().split())
except:
	(n, q) = (0, 0)
(city, ncity) = ([], [])
dp = {}
for _ in range(n + 1):
	city.append([])
	ncity.append([])
for i in range(n - 1):
	(x, y, w) = map(int, input().split())
	city[x].append([y, w])
	city[y].append([x, w])
t = [1]
while len(t):
	c = t[-1]
	t = t[:-1]
	for i in city[c]:
		ncity[c].append(i)
		dp[i[0]] = [c, i[1]]
		t.append(i[0])
		for j in city[i[0]]:
			if j[0] == c:
				city[i[0]].remove(j)
				break
city = ncity
for i in range(q):
	x = list(map(int, input().split()))
	r = x[0]
	s = x[1]
	an = 0
	while r != s:
		if r > s:
			an = an + dp[r][1]
			r = dp[r][0]
		else:
			an = an + dp[s][1]
			s = dp[s][0]
	if r == x[0] or r == x[1]:
		if x[0] < x[1]:
			an = an + 2 * max(up(dp, x[0]), down(city, x[1]))
		else:
			an = an + 2 * max(up(dp, x[1]), down(city, x[0]))
	else:
		an = an + 2 * up(dp, r)
	print(an)