{"problem":{"name":"[USACO23OPEN] Triples of Cows P","description":{"content":"There are initially $N-1$ pairs of friends among FJ's $N$ cows labeled $1\\dots N$, forming a tree. The cows are leaving the farm for vacation one by one. On day $i$, the $i$ th cow leaves the farm, an","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9194"},"statements":[{"statement_type":"Markdown","content":"There are initially $N-1$ pairs of friends among FJ's $N$ cows labeled $1\\dots N$, forming a tree. The cows are\nleaving the farm for vacation one by one. On day $i$, the $i$ th cow leaves the\nfarm, and then all pairs of the $i$ th cow's friends still present on the farm\nbecome friends. \n\nFor each $i$ from $1$ to $N$, just before the $i$ th cow leaves,  how many\nordered triples of distinct cows $(a,b,c)$ are there such that none of $a,b,c$\nare on vacation, $a$ is friends with $b$, and $b$ is friends with $c$?\n\n## Input\n\nThe first line contains $N$.\n\nThe next $N-1$ lines contain two integers $u_i$ and $v_i$ denoting that cows\n$u_i$ and $v_i$ are initially friends.\n\n## Output\n\nThe answers for $i$ from $1$ to $N$ on separate lines.\n\n[samples]\n\n## Note\n\nFor the first sample:  \n$(1,2,3)$ and $(3,2,1)$ are the triples just before cow $1$ leaves.  \nAfter cow\n$1$ leaves, there are less than $3$ cows left, so no triples are possible.\n\nFor the second sample:  \nAt the beginning, cow $1$ is friends with all other cows, and no other pairs of\ncows are friends, so the triples are $(a, 1, c)$ where $a, c$ are different cows\nfrom $\\{2, 3, 4\\}$, which gives $3 \\cdot 2 = 6$ triples.  \nAfter cow $1$ leaves, the remaining three cows are all friends, so the triples\nare just those three cows in any of the $3! = 6$ possible orders.  \nAfter cow $2$ leaves, there are less than $3$ cows left, so no triples are\npossible.  \n\n$2\\le N\\le 2\\cdot 10^5$, $1\\le u_i,v_i\\le N$.\n\n- Inputs 4-5: $N\\le 500$.\n- Inputs 6-10: $N\\le 5000$.\n- Inputs 11-20: No additional constraints.","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9194","tags":["数学","USACO","并查集","2023","仙人掌","圆方树"],"sample_group":[["3\n1 2\n2 3\n","2\n0\n0\n"],["4\n1 2\n1 3\n1 4\n","6\n6\n0\n0\n"],["5\n3 5\n5 1\n1 4\n1 2\n","8\n10\n2\n0\n0\n"]],"created_at":"2026-03-03 11:09:25"}}