{"problem":{"name":"Avoid Straight Line","description":{"content":"You are given a tree with $N$ vertices. The vertices are numbered from $1$ through $N$, and the $i$\\-th edge connects vertex $A_i$ and vertex $B_i$.   Find the number of tuples of integers $(i,j,k)$ s","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc312_g"},"statements":[{"statement_type":"Markdown","content":"You are given a tree with $N$ vertices. The vertices are numbered from $1$ through $N$, and the $i$\\-th edge connects vertex $A_i$ and vertex $B_i$.  \nFind the number of tuples of integers $(i,j,k)$ such that:\n\n*   $1 \\leq i < j < k \\leq N$; and\n*   the given tree does not contain a simple path that contains all of vertices $i$, $j$, and $k$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq A_i, B_i \\leq N$\n*   The given graph is a tree.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$\n$A_1$ $B_1$\n$\\vdots$\n$A_{N-1}$ $B_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc312_g","tags":[],"sample_group":[["5\n1 2\n2 3\n2 4\n1 5","2\n\nTwo tuples satisfy the conditions: $(i,j,k) = (1,3,4),(3,4,5)$."],["6\n1 2\n2 3\n3 4\n4 5\n5 6","0"],["12\n1 6\n3 4\n10 4\n5 9\n3 1\n2 3\n7 2\n2 12\n1 5\n6 8\n4 11","91"]],"created_at":"2026-03-03 11:01:14"}}