Help on a random atcoder problem.

Revision en1, by little_dog, 2024-07-01 09:20:06

Problem Link: https://atcoder.jp/contests/dwacon6th-final/tasks/dwacon6th_final_c

Statement

Given a tree with $$$n$$$ nodes, edge $$$i$$$ connects node $$$(u_i,v_i)$$$. For a permutation $$$p_1,p_2,\ldots,p_{n-1}$$$, the cost of it is defined as follows:

  • For each $$$i$$$ from $$$1$$$ to $$$n-1$$$, in this order, do the following:
    • Let $$$U = u_{p_i},V = v_{p_i}$$$ and $$$x = \text{degree}_U,y = \text{degree}_V$$$, get $$$x \cdot y$$$ points and delete this edge, then merge node $$$U,V$$$ into one node.
  • The cost of permutation $$$p$$$ is the sum of points you get.

Count the total cost of all $$$(n-1)!$$$ permutations, modulo $$$998244353$$$.

What is merging nodes ?
Questions about the official solution

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English little_dog 2024-07-08 12:37:48 15
en2 English little_dog 2024-07-08 12:36:01 207
en1 English little_dog 2024-07-01 09:20:06 1244 Initial revision (published)