CF960E Alternating Tree

树上 DP。

考虑每一条经过 $u$ 的路径的走向，可分为 $3$ 类。

• 子树 $\rightarrow u\rightarrow$ 其他。

• 其他 $\rightarrow u\rightarrow$ 子树。

• 子树 $\rightarrow u\rightarrow$ 子树。

我们设 $s[u][0]$ 表示以 $u$ 为根的子树中距离 $u$ 为偶数的点数，$s[u][1]$ 表示以 $u$ 为根的子树中距离 $u$ 为奇数的点数。

• 对于情况 $1$，贡献为 $(s[u][0]-s[u][1])\times w[u]\times(n-sz[u]+1)$，$w[u]$ 表示点权，$sz[u]$ 表示子树节点数。

• 对于情况 $2$，我们要统计 $u$ 上方（即深度小于 $u$）的距离 $u$ 为奇数或偶数的点数，分别为 $f[u][0]$ 和 $f[u][1]$，那么贡献为 $(f[u][0]-f[u][1])\times w[u]\times sz[u]$，考虑计算 $f$，我们将节点按照深度排序之后就有 $f[u][0]=f[fa[u]][1]+s[fa[u]][1]-s[u][0],f[u][1]=f[fa[u]][0]+s[fa[u]][0]-s[u][1]$。

• 对于情况 $3$，贡献为 $(s[v][1]-s[v][0])\times w[u]\times(sz[u]-sz[v]-1)+(sz[u]-1)\times w[u]$，分别表示 $u$ 子树向下和 $u$ 节点向下。

没了，坑点主要在于关于 $u$ 自身的讨论。

code