# 【模板】树上前缀排序（雾）

5
1 1 3 2
abbaa

1 5 4 2 3

## 题解

I may have a $O(n)$ ideal….

The set of character is really small

Firstly , if we have a trie , we could sort all the paths which are from the node to the root by DFS in $O(n)$ time.

So how could we get the tree ?

find every point’s father is given by the order of the number , the char of root is meaningless to the other paths….So we let the edge to the father own the char.

Each Node has a vector to save numbers , and a a array size of 26 to $O(1)$ check if the father has the $c_i$ or transfer to $c_i$

suppose the current point is $i$ , the char is $c_i$ , the father is $f_i$ , we use a array size of 26 to $O(1)$ check if the father has the $c_i$ , if the father has the $c_i$ , we push the number to the vector of the Node…

The correctness of this is same as the normal tree proof:

when father is the root , it’s apparently right .

else

if the node p , q have same char from the the father , we merge it..

consider the subtree.

let s is p’s son , t is q’s son , if $c(s) = c(t)$ , the situation of two node is right , the correctness is depend on sons.

if $c(s) \ne c(t)$ , it is ordinary situation , which depend on the correctness of father..

we used inductive method.

Emmmm , could you understand the proof above ?

Or we could prove the each path on given tree , has the only path on the tree we create.

So the complexity is $O(n)$ , code will be finished tomorrow because Toto ask me some inclusion-exclusion principle problems….

Writing the code…..

40pts到手（打爆力明题意）