D. Score of a Tree
题目链接：https://codeforces.com/contest/1777/problem/D
个人感觉还是比较简单的一道计数题
题意是给你一颗有n(n<=2e5)节点的树，初始时每个节点有一个值0/1，每过一个时刻值变为子节点的值的异或和，若无子节点则变为0，问对于所有初始情况，每一种情况的所有时刻的树上的点权和之和为多少。
容易发现，对于一个节点，当它为叶子节点时，其取值为1的情况有（1<<n)/2种；
对于多个子节点的节点，设子节点个数为k,则有∑\({k \choose 2i+1}\)种情况其下一时刻为1，易知此时即为（1<<(n-1))种情况在某一时刻（子节点尚未全变为0）其为1。经分析，答案即为每次取树的所有尚存在的节点，乘上（1<<(n-1))后加入答案中，再删掉所有叶子节点，所得即为答案。
上代码：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+10,M=2e6+10,mod=1e9+7;
int ver[M],h[N],nex[M],d[N],tot,f[N];
void al(int x,int y){
ver[++tot]=y;
nex[tot]=h[x];
h[x]=tot;
}
int qpow(int x,int y){
int res=1;
while(y){
if(y&1) res=res*x%mod;
x=x*x%mod;
y>>=1;
}
return res;
}
void dfs(int x,int fa){
f[x]=fa;
for(int i=h[x];i;i=nex[i]){
int y=ver[i];
if(y==fa) continue;
dfs(y,x);
d[x]=max(d[x],d[y]+1);
}
if(!d[x]) d[x]=1;
}
void solve(){
int ans=0;
int n;cin>>n;
tot=0;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
al(u,v),al(v,u);
}
dfs(1,0);
for(int i=1;i<=n;i++){
ans=(ans+d[i])%mod;
}
ans=ans*qpow(2,n-1)%mod;
cout<<ans<<endl;
for(int i=1;i<=n;i++){
ver[i]=0,h[i]=0,nex[i]=0;
d[i]=0;
f[i]=0;
}
}
signed main(){
int T;cin>>T;
while(T--) solve();
}