题解思路

关键分析

1. 最短路径树的性质：

   • 输入的边构成一棵以节点 $0$ 为根的树
   • 每个节点到根节点 $0$ 的路径是原图中的最短路径

2. 合法边的条件：

   • 对于节点 $v$ ，其父节点为 $u$ ，边 $(u,v)$ 必须存在于所有可能的原图中
   • 可以添加的边不能导致出现比树中路径更短的路径
   • 合法边包括：
     • 同层节点之间的边（不改变最短路径长度）
     • 连接到父节点所在层的边（不改变最短路径长度）

3. 组合计数方法：

   • 每个节点 $v$ 的可选边数为其父节点的子节点数（即兄弟节点数 $+ 1$ ）
   • 总可能性为所有节点的可选边数之积

算法设计

我们可以通过以下步骤解决问题：

1. 构建邻接表表示树
2. 通过 BFS 或 DFS 计算每个节点的深度
3. 统计每个深度的节点数目
4. 初始化答案为 $1$
5. 遍历每个节点 $v$（从 $1$ 到 $n-1$ ）：
   • 计算节点v的父节点的子节点数 $s$
   • 答案乘以 $s$ 并对 $10^9+7$ 取模
6. 输出答案

代码实现

以下是该算法的 C++ 实现：

#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1e6+10,M=1e6+10,mod=1e9+7;
int idx,h[N],e[M],ne[M];
int n,dep[N],cnt[N];
//dep[i]表示第i个节点的深度
//cnt[i]表示深度为i的点的个数
void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void dfs(int u,int depth){
    dep[u]=depth;
    for(int i=h[u];i!=-1;i=ne[i]){
        int j=e[i];
        dfs(j,depth+1);
    }
}
int qmi(int a,LL b){
    int res=1;
    while(b){
        if(b&1) res=(LL)res*a%mod;
        a=(LL)a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    dfs(0,0);
    for(int i=1;i<=n;i++){
        cnt[dep[i]]++;
    }
    LL c=0; //计算合法边的数量
    for(int i=1;i<=n;i++){
        c+=(LL)cnt[i]*(cnt[i]-1)/2; //同一深度层内的边数目(组合数C(n,2))
        c+=(LL)(cnt[i]-1)*cnt[i+1]; //相邻深度层之间的边数目
    }
    cout<<qmi(2,c)%mod<<endl; //每一条合法边有存在或不存在两种状态
    return 0;
}