抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

这题其实就是点分治的一个扩展。

此题恶臭,心态被搞了。 考虑SolveSolveSolve算法,每个点有且仅有一次被当做树的根,于是可以将整个算法的期望时间复杂度变成每个点的树的期望大小之和。 想到这里,你还得有一个更加恶臭的想法,考虑如何表示每个点的树的期望大小,记p[i][j]p[i][j]p[i][j]为jjj在iii子树里面的概率。 那么iii子树的期望大小即是∑j!=ip[i][j]\sum _{j!=i} p[...

传送门 考虑点分治,Calc()Calc()Calc()函数如何实现呢?,我们把uuu子树内以根节点为端点的链的长度全部存到一个栈里面,将栈排一个序,令f(i)f(i)f(i)为使得stk[i]+stk[j]≤kstk[i]+stk[j] \le kstk[i]+stk[j]≤k的最小的jjj,考虑把这个式子转换成stk[j]≤k−stk[i]stk[j] \le k-stk[i]stk[j...

传送门 一道非常模板的点分治,核心函数是Calc()Calc()Calc(),返回当前子树中,经过根节点的链有多少条长度是333的倍数,实现时,记录f0,f1,f2f_0,f_1,f_2f0​,f1​,f2​,分别代表有多少条以根节点为端点的链长度mod  3=0,1,2\mod 3=0,1,2mod3=0,1,2,最后乘法原理相乘即可。 注意容斥原理,要减去两条链共用一条根节点发出的边的情...