线性期望dp 因为是求最终被染色的节点数，对于每个节点分开考虑 如果第i个节点被在k次操作里染色的概率为p，则它的对期望的贡献为 pi*1；所以总的期望E = 所有节点被选的的概率之和。对于第i个节点被选的概率不好求，但是可以求它的对立事件，在k次操作里面都不被选的概率q，所以p = 1-q； 一次的所有选择两个点的情况为C（n，2）+n（一个节点被选两次）。一个点不被选的所有情况即为 每次选的点都是子树里面的两个点。 代码： #include<bits/stdc++.h> using namespace std; typedef long long ll; const int N...

H-游戏 矩阵快速幂 考点是邻接矩阵的n次方的意义 考虑矩阵乘法的定义： 令 C=A×B C=A×B Cij=∑k=1nAik×Bkj Cij=∑k=1nAik×Bkj 那么 A2ij=∑k=1nAik×Akj Aij2=∑k=1nAik×Akj 邻接矩阵A中的元素都是用0,1来表示是否联通的，或者说，代表有没有方法从i走到j。那么， Ai,k×AkjAi,k×Akj就是表示从i走到k再走到j是否可行。可以发现， A2A2就是取了一个 ΣΣ，其实就是统计用2步从i走到j的方法总数。 考虑累乘的效果，矩阵 （A的m）ij次方所代表的意义就是从点i到点j之间走m步能够到达的方案总数。 代码： ``...

//对于每个节点来说它的最小消费肯定是以他文根节点， 所有子节点传递过来的最小的两个； 如果每个节点都跑一遍树形dp是O（n方）会t； 我们先固定一个根节点跑一遍dfs，确定它的最小消费； 然后对于剩下的节点，他们的消费已经是除根结点外的所有子节点的最小消费，因此，我们只是需要判断根节点更新它需要的消费会不会更小，如果会就更新； 不可能存在子节点用本身的消费+边权去更新父节点， 然后换根dp后父亲节点又更新子节点;因为大小关系. 其实某一点一定是从子节点或者父亲结点更新过来的，这点也能看出是换根法 #include<bits/stdc++.h> using namespace st...