For a vertex \(v\), let us say \(x\) and \(y\) are in the same side if \(x = v\), \(y = v\), or the simple path connecting \(v\) and \(x\) and another connecting \(v\) and \(y\) has a common vertex that is not \(v\).

When there is no simple path containing vertices \((i,j,k)\), vertices \(j\) and \(k\) are in the same side w.r.t. (with respect to) \(i\); similarly, \(k\) and \(i\) are in the same side w.r.t \(j\); \(i\) and \(j\) w.r.t. \(k\). Thus, there is a unique vertex \(v\) such that any two different vertices among \(i,j\), and \(k\) are not in the same side w.r.t. \(v\). Conversely, if there is a simple path containing all of \((i,j,k)\), there is no such \(v\).

Thus, it is sufficient to count the tuples \((i,j,k)\) such that any two different ones among them are not in the same side w.r.t. \(v\) for all \(v = 1,2, \ldots, N\); then the answer is the sum of the counts.

We now consider a subproblem where \(v\) is fixed. Suppose that the tree is rooted at \(v\), and its children are \(w_1, w_2, \ldots, w_n\). \((i,j,k)\) satisfies the condition if and only if there are distinct \((i', j', k')\) such that vertices \(i\), \(j\), \(k\) are in the subtrees rooted at \(w_{i'}\), \(w_{j'}\), and \(w_{k'}\), respectively. Thus, the answer is the sum of \(c_{i'}c_{j'}c_{k'}\) over distinct \((i', j', k')\), where \(c_l\) is the number of vertices contained in the subtree rooted at \(w_l\).
Therefore, it is sufficient to, given a sequence \(c\), find the sum of products of three distinct elements; this can be computed in a total of \(O(|c|)\) time with a DP (Dynamic Programming) where \(dp_{i,j}\) is the sum of products of \(j\) distinct elements chosen from the first \(i\) elements. (If you are used to discussions on combinatorics with polynomials, it may be simpler to consider it as \([x^3] \displaystyle \prod (c_ix+1)\).)

Hence, the subproblem for a fixed \(v\) is solved. The only information that we need is the number of vertices in the subtree rooted at each child of \(v\) when the tree is rooted at \(v\); this can be found fast enough by taking an arbitrary vertex as a root and doing a tree-DP to find the size of the subtree rooted at each vertex. Since the complexity for a vertex \(v\) is \(O(d(v))\) where \(d(v)\) is the degree of \(v\), so the problem has been solved in a total of \(O(N)\) time.