这题真的很套路，很没意思。 考虑换根dp，然后就是爆拆式子： （AAA为除去uuu之后的uuu子树，BBB为除去vvv之后的vvv子树） 以uuu为根： ∑i∈Adis(i,u)2c[i]+w2c[v]+∑i∈Bdis(i,u)2c[i]\sum _{i\in A}dis(i,u)^2 c[i]+w^2c[v]+\sum _{i\in B}dis(i,u)^2c[i]∑i∈A​dis(i...

传送门 考虑预处理出szszsz数组，表示子树的大小，处理出来val[u]val[u]val[u]数组，表示uuu的子树里面的所有奶牛到uuu集合的不方便度。 于是dpdpdp就十分简单，初始化dp[1]=val[1]dp[1]=val[1]dp[1]=val[1]，然后考虑集合地点从uuu变到vvv，vvv子树里面的所有奶牛都会少走www路程，而剩下奶牛都会都走www路程。 1234567...

传送门 这个题目背景真的是太孙了，必须吐槽！ ProProPro 给一棵树，每个点有一个权值，要求修改一些权值，使： 一个点的权值必须是其所有儿子的权值之和 一个点的儿子权值必须相同 求最少的被修改的数目 SolSolSol 其实此题充满套路的气息，首先，如果一个节点的权值确定，整个树都会确定。 假设节点uuu的权值是val[u]val[u]val[u]，孩子数量是son[u]son...

最小支配集的定义：给你一棵树，让你选出一些节点，选出来的节点会把自己和相邻的节点全部覆盖，让你求出选出来节点的最小数量。 考虑树形dp： 定义: dp[i][0]dp[i][0]dp[i][0]: 点iii属于支配集，并且以点iii为根的子树都被覆盖了的情况下支配集中包含的最少点数 也就是iii支配自己 合法状态举例（不一定最少） dp[i][1]dp[i][1]dp[i][1]: 点ii...

传送门 先上一个结论，所有kkk个节点应该构成一棵树，形状是原树的直径连着一堆子树，其中直径只经过一遍，子树的所有边经过两次，走法就是从直径的一段走到另一端，但是中途会离开直径，到某个和当前节点相连的子树逛一圈再回到这个节点。 所以子状态就有了，dp[u][j][0/1/2]dp[u][j][0/1/2]dp[u][j][0/1/2]表示uuu的子树里面选jjj个点，而且uuu的子树里面有多...

传送门 考虑dp状态dp[u][i][0/1][0/1]dp[u][i][0/1][0/1]dp[u][i][0/1][0/1]表示dp到节点uuu，uuu的子树里面放了iii个监听设备，uuu自己有没有被放，uuu自己有没有被监听。 注意到我们要满足题目的条件，所以只有u的子树内的其他点（不包含u）都被监听，才会算入dp方案数。 接下来是恶心的分类讨论： 1.dp[u][i][0][0]1...

传送门 不记得是哪场比赛切的题了，发现点ppp的两个不同子树中任选两个点作为(ui,vi)(u_i,v_i)(ui​,vi​)，他们的LCALCALCA 都是pip_ipi​ 所以答案为∑u,v∈ch[p],u!=vsz[u]∗sz[v]\sum_{u,v \in ch[p],u!=v} sz[u]*sz[v]∑u,v∈ch[p],u!=v​sz[u]∗sz[v]，剩下容斥乱搞一下就可以了。...