Codeforces 1777D. Score of a Tree

题意：

    给你一颗个节点并且以  为根节点的树，在  时刻的时候，每个节点的权值为或

    在每个 时，每个结点的值都会变成其子结点在  时的值的异或和，同时叶子节点的权值变为 ，因为其没有子节点。

    定义为  时所有节点值的和

    定义为树在  中所有  的和。其中  为树在时刻  时每个结点的值。

求所有  个  的和。

思路：

•     首先，因为叶子节点会变成 ，那么所有节点最后都会变成 ，沿着这个思路思考会发现，在  时刻，深度为  及以下的所有节点值都为 ， 所以每个节点只能在 的时刻内才会对答案有贡献（ 为以节点为根的最长链的长度）

• 其次，根据异或性质，如果某个节点有个儿子节点，那么奇数个  异或起来最后该节点对答案才会有贡献，那么在所有情况下，该点对答案的贡献应该是 ，根据组合数公式，该值为

• 最后，对于任意一点，这个点在全局的贡献即为他在的时刻所产生的贡献，即