ssoj4021: 西行妖下（yuyuko）

題意：有一顆n個節點的樹，初始時每個節點上有一個長度為1的排列，有q次操作，每次操作給出u，v可将u到v的路徑上排列長度乘或加上x，或詢問u到v路徑上，若将每個節點的排列随機，這條路徑節點上排列為錯排的節點個數的期望。n，q<=8e4,x<=1e4.答案保留一位小數。

題解:

有賴于我極爛的數學功底和打表找規律能力，考場時一看到就覺得不可做（若真的去加、乘，且不說高精了，錯排的機率都沒法算啊）。那麼，對于這麼看起來不可做的題目，一定有什麼玄學的性質使它可做。考慮錯排機率的計算，它是一個遞推式，故若要真的去算要O(N)，顯然不可行；而通項公式好像也不太可推（即使推出，節點資訊也要用高精存，不太可行）。注意到竟然隻要保留一位小數，那是什麼意思呢？即每個節點的資訊精确到五位小數即可，而機率在0——1之間，最多隻有1e5種情況，考慮如何将長度對應到這些值，通過打表發現:到長度20之後，值的變動在1e5之内，即數列收斂（無需嚴格證明，因為看着很顯然），那就很可做了，對于一個節點，若長度超過20，就打個标記，無需再更新，對于樹上路徑修改、查詢問題，樹剖即可，且對于區間修改，不用在區間上标記，直接下傳到葉子即可，因為這樣的次數不會很多(一個區間内所有節點都到20就不再通路了)。