這次比賽炸了。
T1：首先我們枚舉i、j兩種試劑，然後我們發現這兩種試劑對所有k影響呈一個梯形（即一段遞增、一段相同、再一段遞減），這個自己推一推就知道了。那麼有了這個性質以後，我們可以用差分套差分來維護答案。這樣這道題就做完了。
總結：考試時我沒有想到差分套差分。對于這種要給序列的某一段加上一個等差數列的題目可以采用這種套路。
T2：首先把樹轉換成圖，然後根據圖來列随機遊走的方程。
具體方程就是對于一個x，設f[x]表示從x走到1的期望步數。那麼對于與x有連邊的點y，我們可以從x走到y，再從y走到1，那麼就有：
，d[x]表示x的度數。
化簡後有：
，然後我們可以得到n-1條方程（因為f[1]=0），這時就可以高斯消元了。
但是這樣消元的複雜度是O(n^3)的。此時我們可以改變消元順序，從n消到1。那麼對于一個i，當消到i的時候，i的所有兒子已經消完了，是以i隻需要和fa[i]以及fa[fa[i]]消，是以複雜度就變成了O(n^2)了。
總結：這種期望問題在樹上一般是樹形dp，而在圖上一般是列方程+高斯消元。
T3：首先對于一個d和i，若i<=d，那麼就會獲得d-i的貢獻；若i>d，那麼就會獲得i-d的貢獻（自己加上i，同時把選擇權交給對方，那麼對方就會期望領先自己d，是以是i-d）。
于是我們得出了方程：
。
化簡就是：
。
現在我們要求一個d使方程成立。
于是設f(x)=
，那麼現在就是求f(x)的零點。
顯然f(x)是減函數（x增大時前半部分比後半部分增加的少），那麼我們首先二分求出d的整數部分k（即f(k)>0,f(k+1)<0）。然後我們就可以把方程中的絕對值去掉，這時剩下來的就是解方程了。