前言

发现我现在树的题什么也不会了。。
就只会树剖和dsu。。

题解

暴力的做法很容易想到
就是枚举两个点，那么他对答案的贡献就是$2^{n-(dep[x]+dep[y]-2*dep[LCA]+1)}$
然后我们胡乱考虑一下，就可以吧答案拆成$2^n/2^{(dep[x]+dep[y]-2*dep[LCA]+1)}$
然后后面这个式子，也是一样可以拆开的
也就是$2^{dep[x]}*2^{dep[y]}/2^{2*dep[LCA]-1}$
于是我们就可以合并子树了
每一个子树里面记录一个$2^{dep[x]}$的和，这个显然可以用dsu优化
然后启发式合并把别的子树合并进去就可以了
时间复杂度是$O(nlogn)$的
做完以后瞄了一眼题解，并不知道题解在讲什么。。

CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MOD=1e9+7;
const LL INV=500000004;
const LL N=100005;
LL pow[N],inv[N];
struct qq {LL x,y,last; }e[N*2];LL num,last[N];
LL n;
void init (LL x,LL y)
{num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;
}
LL ans=0;
LL tot[N],son[N];
LL dep[N];
void dfs1 (LL x,LL fa)
{tot[x]=1;for (LL u=last[x];u!=-1;u=e[u].last){LL y=e[u].y;if (y==fa) continue;dep[y]=dep[x]+1;dfs1(y,x);tot[x]=tot[x]+tot[y];if (tot[y]>tot[son[x]]) son[x]=y;}
}
LL lalal;
LL p;
LL o;
void solve (LL x,LL fa)
{ans=(ans+o*lalal%MOD*inv[dep[x]]%MOD*pow[p]%MOD*pow[p-1]%MOD)%MOD;for (LL u=last[x];u!=-1;u=e[u].last){LL y=e[u].y;if (y==fa) continue;solve(y,x);}
}
void add (LL x,LL fa)
{lalal=(lalal+inv[dep[x]])%MOD;for (LL u=last[x];u!=-1;u=e[u].last){LL y=e[u].y;if (y==fa) continue;add(y,x);}
}
void dfs (LL x,LL fa)
{for (LL u=last[x];u!=-1;u=e[u].last){LL y=e[u].y;if (y==fa||y==son[x]) continue;lalal=0;dfs(y,x);}if (son[x]!=0)  {lalal=0;dfs(son[x],x);}p=dep[x];for (LL u=last[x];u!=-1;u=e[u].last){LL y=e[u].y;if (y==fa||y==son[x]) continue;solve(y,x);add(y,x);}ans=(ans+o*lalal%MOD*pow[p-1]%MOD)%MOD; lalal=(lalal+inv[dep[x]])%MOD;
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%lld",&n);pow[0]=1;for (LL u=1;u<=n;u++) pow[u]=pow[u-1]*2%MOD;o=pow[n];inv[0]=1;for (LL u=1;u<=n;u++) inv[u]=inv[u-1]*INV%MOD;for (LL u=1;u<n;u++){LL x,y;scanf("%lld%lld",&x,&y);init(x,y);init(y,x);}dep[1]=1;dfs1(1,0);dfs(1,0);printf("%lld\n",ans);return 0;
}