今天开始换湖南的题了，前几天一直在考山东的省队集训，感觉之前题目非常毒瘤而且不给部分分，没有写题解的欲望。

T1

给出一棵n个点的树，支持换根、子树权值加、求子树权值和，查询LCA，n<=3e5。

如果不涉及LCA，那么只要求出DFS序之后讨论一下即可。

对于换根求LCA，我们只需要先求u和root的lca还有v和root的lca，如果不同，则u和v一定处于root到原来根的路径上的两棵子树，这时候我们只需要找到较深的那个即可。如果相同，则为u和v的lca，之后这道题就做完了。

另外，如果想用LCT求LCA，只需要access(u)，然后在access(v)后的那个splay根就是答案。为什么？模拟一下就好了。但是这样因为常数太大而无法通过。

 

T2

题意略。

首先，对于询问(x,y)，答案为\(f(x,y)=min_{i}{sum(y)-sum(i)+(x-y)\,S(i)+i\,S(i)}\)。

之后，发现这是个斜率优化的式子，就是令\(b=f - sum(y)\)，\(y=i\,S(i) - sum(i)\)，\(x=S(i)\)，我们想最大化截距。

把每个决策点看成点(x,y)，那么对于两个决策点i和j，如果i<j且s(i)>s(j)，那么i一定不优，因此我们需要保证点的横坐标单调递增，且需要形成一个下凸包，维护就好了。

计算答案的时候直接在凸包上三分或者二分就好了。因为精度问题，我选择了差积判断凸包以及三分凸包算答案的方法，这样做不设计斜率的计算，精度也就有了保证，虽然三分会慢一些。

 

T3

另序列B表示序列A的前缀按位或和，计算在A中元素小于2^k且B单调递增的情况下的A的个数。

首先如果我们直接令f[i][j]表示i个数用了j位（考虑空位），那么我们就可以通过NTT优化到O(nklogk)，获得59分。

之后，可以改一下DP数组的定义，我们不需要考虑没有使用的空位，只需要维护数位之间的相对标号即可，这样转移的话可以倍增进行，转移的式子就是\(f[a+b][x]=\sum_{i=0}^{x-1}f[a][i]*f[b][x-i]*C_{x}^{i}2^{bi}\)。复杂度O(klognlogk)。