題意：

????給你一顆個節(jié)點并且以??為根節(jié)點的樹，在??時刻的時候，每個節(jié)點的權值為或

????在每個 時，每個結點的值都會變成其子結點在??時的值的異或和，同時葉子節(jié)點的權值變?yōu)?，因為其沒有子節(jié)點。

????定義為??時所有節(jié)點值的和

????定義為樹在 ?中所有??的和。其中??為樹在時刻??時每個結點的值。

求所有??個??的和。

思路：

• ????首先，因為葉子節(jié)點會變成?，那么所有節(jié)點最后都會變成?，沿著這個思路思考會發(fā)現，在??時刻，深度為??及以下的所有節(jié)點值都為?， 所以每個節(jié)點只能在?的時刻內才會對答案有貢獻（?為以節(jié)點為根的最長鏈的長度）

• 其次，根據異或性質，如果某個節(jié)點有個兒子節(jié)點，那么奇數個??異或起來最后該節(jié)點對答案才會有貢獻，那么在所有情況下，該點對答案的貢獻應該是?，根據組合數公式，該值為

• 最后，對于任意一點，這個點在全局的貢獻即為他在的時刻所產生的貢獻，即?