真的是公公又式式啊
换根dp的宗旨是利用已有的信息来推出其他信息
换根dp的题目通常是树，o(n)时间空间，要求每一个点的答案。
我们如果指定了以1为根，那么可以算出每个点往下的答案，但是每个点的父亲对本身的贡献还没有算，所以我们可以记录dp1,dp2两个数组，分别记录
专用图
注意，dp1[u]记录的是u下的子树,dp2[u]记录的是2号子树的答案，所以dp2[to]就是通过1号子树，u和dp2[u]的合并得到答案
P3478
我们指定1为根，那么可以算出每个点往下的答案
\[dp1[u]=siz[u]-\sum dp1[u] \]\[dp2[to]=dp1[u]+dp2[u]+siz[1]-siz[to] \]\[ans[u]=dp1[u]+dp2[u] \]当然还有更简单的方法，每次从u到to，to的子树里节点深度都减1，其他节点深度+1
\[dp[to]=dp[u]-siz[to]+n-siz[to] \]CF708C
需要转化，发现如果一个点如果是重心那不用改，如果不是那必然会有一个子树大小大于n/2，我们需要从这颗子树里再剥出一棵子树，剥出来的子树大小小于等于n/2并且剥完之后子树大小小于等于n/2。有个简单的贪心就是所以我们设计dp1[u]为u向下的最大的大小小于等于n/2的子树大小，dp2[u]为u向上的最大的大小小于等于n/2的子树大小。
\[if(siz[u]<=n/2) \ dp1[u]=siz[u] \]\[else\ dp1[u]=min(dp1[to]) \]\[if(n-siz[u]<=n/2)\ dp2[u]=n-siz[u] \]\[else\ dp2[to]=min(dp1[to],dp2[u]) \]记得在做to时不要把to算进去
CF543D
首先我们设dp[u][0]为子树内全修的方案数，dp[u][1]为子树内一部分修的方案数，两者都保证合法。发现dp[u][0]始终=1，于是压掉一维。那么这题有两种转移方法，一种是\(dp[u] =(\prod dp[to]+2)-1\)意思是如果这条路要修的话下面任意，如果下面全都修了那么这条路会有两种方法，然后有一种方案和dp[u][0]重了，要减掉
还有一种方法是\(dp[u]=\prod dp[to]+1\)，意思是如果这条路修的话下面任意，不修的话就是下面全要修。
然后我们dp1[u]就是正常搞，dp2[to]就等于1号子树+2的乘积乘上dp[u]+2，然后ans[u]=dp1[u]*(dp2[u]+2)-1，逆元用前缀积+后缀积即可。
标签：三题,子树,dp2,dp1,siz,换根,dp From： https://www.cnblogs.com/wuhupai/p/18313732