This problem came in their coding challenge. Can anyone solve it ?

Problem Statement

You are given a tree with n nodes and n-1 edges. The nodes are numbered from 1 to n. Each edge has a weight, either 1 or -1.

You need to count all pairs of nodes (u, v) such that:

• Node u != Node v

• There exists a node x in simple path between u and v such that u != v != x

• Let F(a, b) = Sum of edge paths between Nodes a and b. Ensure that F(u, x) = F(v, x) = 0.

Constraints

1 <= n <= 1000000

Test Case

N = 8

Edges. (Format used :- Node x, Node y, Edge Weight)

(1, 3, 1) -> (Nodes 1. Node 3. Edge Weight 1)

(3, 2, -1)

(2, 6, 1)

(2, 5, -1)

(5, 4, 1)

(5, 7, -1)

(7, 8, 1)

Ans:- 2.

Explanation:-

Node u = 1, v = 4, x = 2. F(1, 4) = F(2, 4) = 0. Node x falls in the path between (u, v)

Node u = 6, v = 8, x = 5. F(6, 5) = F(8, 5) = 0. Node x falls in the path between (u, v)

Can anyone please help ?