### little_dog's blog

By little_dog, history, 3 months ago,

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 ?

UPD: I read the some AC code and find that the answer is $(n-1)! \cdot (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 :(

• +7

By little_dog, history, 6 months ago,

I found a SAM solution on luogu, but it is too hard for me to learn SAM, I wonder if there exists a solution without SAM.

Problem statement

UPD: I solved it with Suffix Array, DSU, KMP, Fenwick tree and Segment tree merging in $\mathcal O(n \log n)$, Yay!

• +11