再次滚粗。今天是打表专场吗
A.给出一棵树，每个点有权值v[i]。m个操作，每次可以修改某个点的权值或者查询从树中选出一个连通块要求sigma(v[i])最大。v[i]可以为负数。n，m<=10W
题解；我只写了50分的暴力
30分n<=1000可以每次树形DP一下。20分链其实就是最大连续子段和。
正解考虑树链剖分。每条重链一棵线段树，但是每个点的权值是它往下连出的轻链的DP值之和。这样我们每次就可以沿重链往上跳了。
DP值之和其实就是线段树的lx。
没做过这种类型的题QAQ
B.求n个点n条边的无向连通图。n<=5000 %30 n<=10
题解：我yy了一个暴力。。。准备打10的表。。。f[n][m]表示n个点，m条边的无向连通图的个数。
那么f[n][m]=C（C（n，2），m）-sigma（sigma(f[i][j]*C(n-1,i-1)*C(C(n-i,2),j)) 。
然后发现爆零了。每个都比ans大
现在还不知道为什么。。。
C.n个白球放成一列，每次随机选择一个合法区间[l,r]将里面的白球全部染白。求期望多少次能把球全部染黑。
题解：CLJWC的题。。。我是真没听懂。。。暴力打表发现每次结果都不一样
评论 (0)
