如果能再给我 30min……
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
F
Difficulty：4.3 / Easy
Tag：-
会发现题目让我们求的是一个二次函数的最大独立集问题。直接建图做是 NP-Hard 的。
对于第 iii 个二次函数，我们可以把它掰成 xxx 轴，然后把其它二次函数相对应的弯曲，也就是把第 jjj 个二次函数变成 y=(aj−ai)x2+(bj−bi)x+(cj−ci)y=(a_j-a_i)x^2+(b_j-b_i)x+(c_j-c_i)y=(aj −ai )x2+(bj −bi )x+(cj −ci )。显然这个不影响最大独立集的数量，而且与 xxx 轴有交点的是不能选的。所以我们可以分成 xxx 轴上方和 xxx 轴下方来讨论，对这两个求最大独立集。显然可以做到 O(n2)O(n^2)O(n2) DP，是个人随便写写都能写出来，什么我没写出来，好像成为人类啊。
G
Difficulty：4.6 / Easy
Tag：-
首先做 E。
定义 sizu\text{siz}_usizu 为从第 iii 个点开始进行一次“Idiot First Search”走完左右子树后回到 iii 的步数。显然有 sizu=1+sizlsonu+1****izrsonu****izlsonu+sizrsonu+4\text{siz}_u=1+\text{siz}_{\text{lson}_u}+1+1+\text{siz}_{\text{rson}_u}+1=\text{siz}_{\text{lson}_u}+\text{siz}_{\text{rson}_u}+4sizu =1+sizlsonu +1****izrsonu
****izlsonu +sizrsonu +4。第 iii 个节点走到节点 000 的步数为它与所有祖先的 siz\text{siz}siz 之和加上 i→0i\rarr 0i→0 的距离。O(n)O(n)O(n)。
注意到这个答案其实一定不超过 4n24n^24n2。所以 109+710^9+7109+7 的限制就当他没用了。
首先求出它会走到那个祖先。这个很简单，倍增二分即可。
然后按 dfn 二分即可，ST表或线段树求。
O(nlogn+qlog2n)O(n\log n+q\log^2 n)O(nlogn+qlog2n)。
