little_dog's blog

By little_dog, history, 4 months ago, In English

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

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 :(

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it

By little_dog, history, 7 months ago, In English

problem link.

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!

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it