T1

签到题，单调栈就好了

T2

求无根树以每个点为根的lca总和

考虑对于每个点算它被用了几次，容易得出公式
再考虑换根节点时的变化量，不难得出变化的数量很小
于是直接枚举变化

T3

数学题
当然也可以找规律（见cqr）

T4

我 不 会！！！！