写了个T1,T3的暴力。
T1显然可以二分答案之后枚举lca，复杂度 O ( n l o g 3 n ) O(nlog^3n) O(nlog3n)有72分，写完调完。
T1因为树的形态随机，所以直接dfs一遍树把所有合法的二元组用数据结构维护就行了。
复杂度
O
(
1
)
−
O
(
n
)
O(1)-O(\sqrt n)
O(1)−O(n)或者
O
(
l
o
g
n
)
−
O
(
l
o
g
n
)
O(logn)-O(logn)
O(logn)−O(logn)感觉分块很悬于是写了线段树二分。
T3是max卷积和异或卷积的拼合体，所以分别做就行了，复杂度 O ( n 2 l o g n ) O(n^2logn) O(n2logn)，有62分。
写T2的暴力
链的部分显然可以用组合数算，又想了一会dp发现不太会。
其实是个很简单的dp，设
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示i的子树内选了j个点access的方案数，然后钦定每个状态被可以得到这个状态的最少花费处计算，考场上没想到这一点。其余部分就是简单地树背包。
还是要练习dp的水平。
异或对于每一位是独立的，因此对于每一位分别用FFT差卷积计算方案数，再用max卷积合并，这样的好处是不需要FWT，复杂度
O
(
n
l
o
g
2
n
)
O(nlog^2n)
O(nlog2n)。
另一种做法是用数位dp统计，不过还没看懂。