题目描述:
给定一棵树,在树上选 \(3\) 个点,要求两两距离相等,求方案数。
数据范围:
\(1\le n\le 5000\)
\(1\le a,b\le n\)
思路:
一开始我想的就是枚举两个点,然后处理第三个点。
但是发现这样做非常的不正确,并且非常容易算重,所以我舍去了这种方式。
但是在想这种做法的时候,我们会发现,如果想要使得三个点距离相同,就等于需要找到两个点的路径中点,然后这个中点与三个点的距离相同。
然后我们又又又发现一件事情,如果这个中点被当成了根,显然现在我们选择的三个点只需要深度相同,距离肯定就都相同了。
所以我们不妨枚举这个中点是哪一个点,我们假设这个点为 \(a\)
然后我们以 \(a\) 为根,所有 \(a\) 的子树中每个子树内最多只能有一个被选择的节点,因为如果超过一个,显然 \(lca\) 就不是 \(a\) 了。
问题转换为在同一深度的节点中,每颗子树内最多选择一个节点且一共选择三个节点的方案数。
然后我们思考这个问题怎么处理?
首先我们令 \(f_i\) 表示在遍历当前这棵子树之前的所有子树中,在深度 \(i\) 选择两个点的方案数是多少;\(g_i\) 表示在遍历当前这棵子树之前的所有子树中,在深度 \(i\) 选择一个点的方案数是多少;\(cnt_i\) 表示当前这棵子树深度为 \(i\) 的数量
可以较为轻松的推出转移方程:
\(ans\leftarrow f_i\times cnt_i\)
\(f_i\leftarrow g_i\times cnt_i\)
\(g_i\leftarrow cnt_i\)
时间复杂度 \(O(n^2)\),空间复杂度 \(O(n)\)
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=5005;
const int inf=0x3f3f3f3f;
int n;
vector<int>G[maxn];
int cnt[maxn],f[maxn],g[maxn];
int mxdep;
void dfs(int u,int f,int dep){cnt[dep]++;mxdep=max(mxdep,dep);for(int v:G[u]){if(v==f)continue;dfs(v,u,dep+1);}
}
void init(){for(int i=1;i<=n;i++)f[i]=g[i]=0;
}
signed main(){scanf("%lld",&n);for(int i=1;i<n;i++){int u,v;scanf("%lld%lld",&u,&v);G[u].push_back(v);G[v].push_back(u);}int ans=0;for(int i=1;i<=n;i++){init();for(int j:G[i]){for(int _=1;_<=n;_++)cnt[_]=0;mxdep=-inf;dfs(j,i,1);for(int k=1;k<=mxdep;k++){ans+=f[k]*cnt[k];f[k]+=g[k]*cnt[k];g[k]+=cnt[k];}}}printf("%lld\n",ans);return 0;
}