前言

或贪心或 dp 地做最优解，或 dp 或二分地解决单调性问题，dp 或组合数学地做计数，或 dp 或数学地做构造，或 dp 或搜索地做图论，或 dp 或数据结构地做可行性，或 dp 或唉声叹气地活着，我们活在 dp 里，当然，这题的 dp 含量很低，只有求深度。

思路

清新图论题。

首先的首先，本题解节点编号为 $1\sim n$，代码中已经做了处理。

首先，实际上，对于所有不影响最短路的边，都是选不选都可以，设这种边的数量为 $ans$，则答案为 $2^{ans}$。

那么接着我们来讨论哪些边不影响，显然给定的图是一颗树，那么我们让 $1$ 号点为根，节点深度 $d_i$ 就是到 $1$ 号点的距离减 $1$，这里不影响答案，我们来看样例 $3$ 的树。

我们给出 $d$ 数组：

显然，对于 $(i,j)$，如果 $d_j>d_i+1$，那么连边后最短路更新了，不能连。考虑到重边，我们只能额外连：

• $d_i=d_j$

• $d_i=d_j+1$

第 $1$ 种的答案是 $\sum^{\infty}_{i=1}d_i\times(d_i-1)\div 2$，很好求。对于第 $2$ 种，对于 $d_i$，除了自己父亲，上一层都有 $d_{i-1}-1$ 条边与自己相连，因此答案是 $\sum^{\infty}_{i=1}(d_i-1)d_{i+1}$。当然这里无限求 $d_i$ 最大即可。

最后求和用快速幂求答案即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,ans,dis[1000005],f[1000005],d[10000005];
vector<int> g[1000005];
void bfs()
{
	queue<int> q;     
	q.push(1);
	f[1] = 1;
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		for (int v : g[u])
		{
			if (!f[v])
			{
				f[v] = 1;
				dis[v] = dis[u] + 1;
				q.push(v);
			}
		}
	}
}
int qpow(int a,int b,int p)
{
	int res = 1;
	while (b != 0)
	{
		if (b % 2 == 1) res = res * a % p;
		a = a * a % p,b /= 2;
		
	}
	return res;
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1,u,v;i < n;i++) 
	{
		cin >> u >> v;
		u++,v++;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	bfs();
	int ma = INT_MIN,ans = 0;
	for (int i = 1;i <= n;i++)
	{
		d[dis[i] + 1]++;
		ma = max(ma,dis[i] + 1);
	}
	for (int i = 1;i < ma;i++)
	{
		ans = ans + (d[i] - 1) * d[i + 1];
	}
	for (int i = 1;i <= ma;i++)
	{
		ans = ans + (d[i] * (d[i] - 1) / 2);
	}
	const int md = 1e9 + 7;
	cout << qpow(2,ans,md);
	return 0;
}

题解思路

关键分析

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;
}