#arc108f. [arc108_f]Paint Tree

[arc108_f]Paint Tree

给定一棵 nn 个节点的树。你需要对每个节点黑白染色。

xx 表示白色点之间的最大距离,yy 表示黑色点之间的最大距离,那么定义一种染色的权值为 max(x,y)\max(x,y)。如果某种颜色没有出现那么对应的 x/yx/y 就是 00

求所有 2n2^n 种染色方式的权值和。对 109+710^9+7 取模。

Data Range:2n2×105\texttt{Data Range:} 2\le n\le 2\times 10^5