**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$.↵
↵
<spoiler summary="What is merging nodes ?">↵
↵
In the following we are merging nodes $1,4$ getting $3 \cdot 3 = 9$ points.↵
↵
↵
↵
(pictures from atcoder problem statement)↵
</spoiler>↵
↵
<spoiler summary="Questions about the official solution">↵
The editorial said that we could rewrite the statement as _For each $k$ counting the number of paths of length $k$_, but why? Can anyone explain that ? The explaination in the editorial is so unreadable that i can't understand at all :(↵
</spoiler>↵
↵
---↵
↵
UPD: I read the some AC code and find that the answer is $a_1 + a_2 + \sum \limits_{i=3}^n \dfrac{4a_i}{i(i-1)}$, where $a_i$ is the number of paths of length $i$. But I still can't understand it :(
↵
**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$.↵
↵
<spoiler summary="What is merging nodes ?">↵
↵
In the following we are merging nodes $1,4$ getting $3 \cdot 3 = 9$ points.↵
↵
↵
↵
(pictures from atcoder problem statement)↵
</spoiler>↵
↵
<spoiler summary="Questions about the official solution">↵
The editorial said that we could rewrite the statement as _For each $k$ counting the number of paths of length $k$_, but why? Can anyone explain that ? The explaination in the editorial is so unreadable that i can't understand at all :(↵
</spoiler>↵
↵
---↵
↵
UPD: I read the some AC code and find that the answer is $a_1 + a_2 + \sum \limits_{i=3}^n \dfrac{4a_i}{i(i-1)}$, where $a_i$ is the number of paths of length $i$. But I still can't understand it :(
