题意：求一棵边权全都是1的树上，集合大小为3，且集合内点两两距离相等的集合个数。
NOIP2014 D1T2加强版。。
通过分析发现，满足这样的点对一定是在有根树中深度相同，且不再同一棵以根节点儿子为根的子树中。
于是我们枚举根。。
三个点的集合个数是由2个点的集合个数转移过来的。。2个又是由一个转移过来的。用两个数组保存一下即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<algorithm> 5 #define p_b push_back 6 const int MAXN=5000+5; 7 std::vector<int> G[MAXN]; 8 typedef std::vector<int>::iterator vit; 9 int n; 10 int fa[MAXN],dep[MAXN],temp[MAXN]; 11 int mx; 12 void dfs(int u) 13 { 14 temp[dep[u]]++; 15 mx=std::max(mx,temp[dep[u]]); 16 for(vit e=G[u].begin();e!=G[u].end();++e) if(*e!=fa[u]) 17 { 18 fa[*e]=u; 19 dep[*e]=dep[u]+1; 20 dfs(*e); 21 } 22 } 23 typedef long long LL; 24 LL t1[MAXN],t2[MAXN],ans; 25 int main() 26 { 27 //freopen("1.in","r",stdin); 28 scanf("%d",&n); 29 for(int i=0;i<n-1;++i) 30 { 31 int u,v; 32 scanf("%d%d",&u,&v); 33 G[u].p_b(v); 34 G[v].p_b(u); 35 } 36 for(int i=1;i<=n;++i) 37 { 38 memset(t1,0,sizeof(t1)); 39 memset(t2,0,sizeof(t2)); 40 for(vit e=G[i].begin();e!=G[i].end();++e) 41 { 42 fa[*e]=i;dep[*e]=1; 43 dfs(*e); 44 for(int j=1;j<=mx;++j) 45 { 46 ans+=t2[j]*temp[j]; 47 t2[j]+=temp[j]*t1[j]; 48 t1[j]+=temp[j]; 49 } 50 for(int j=1;j<=mx;++j) temp[j]=0; 51 } 52 } 53 printf("%lld ",ans); 54 }