先看了一遍题，感觉一道都不会，非常自闭。
写了T2的暴力。
写T3的暴力
写T3的第二和第三档，但是不知为什么答案总是会大。
于是就放弃了
T1可以斯特林拆幂之后容斥做，但是不知道为什么答案总是不对。自闭。
想了想T2的 O ( n 2 ) O(n^2) O(n2)，写完过了大样例。
就是套路的用斯特林数拆幂，转化为组合意义，然后通过容斥进行dp，总之就是非常套路。
考试的时候有个细节写错了，导致挂了。
dsu on tree，然后用树链剖分统计
d
[
y
]
−
2
∗
c
n
t
[
x
]
[
y
]
d[y]-2*cnt[x][y]
d[y]−2∗cnt[x][y]
复杂度
O
(
n
l
o
g
3
n
)
O(nlog^3n)
O(nlog3n)，但是常数不大。不过非常好些。
用线段树合并维护，然后还是树链剖分，不过空间是
O
(
n
l
o
g
2
n
)
O(nlog^2n)
O(nlog2n)，很危险。
于是把每一条重链公用一棵线段树，于是空间单log。
就是dp，只不过出题人实现的更妙。
待upd。