題目大意：給定一棵樹，求有多少無序三元組(x,y,z)滿足x,y,z互不相等且Dis(x,y)=Dis(y,z)=Dis(x,z)
三個點在樹上有兩種情況
第一種是三點共鏈 第二種是存在且僅存在一個中心點滿足三個點分別在這個點的三個不同的出邊的方向
第一種情況顯然無解
第二種情況一定滿足三個點到中心點的距離相等
由於n<=5000因此直接枚舉中心點然後枚舉中心點的每一條出邊DFS即可
時間復雜度O(n^2)
#include
#include
#include
#include
#define M 5050
using namespace std;
struct abcd{
int to,next;
}table[M<<1];
int head[M],tot;
int n;
long long ans;
int temp[M],f[M],g[M];
void Add(int x,int y)
{
table[++tot].to=y;
table[tot].next=head[x];
head[x]=tot;
}
void DFS(int x,int from,int dpt)
{
int i;
temp[dpt]++;
for(i=head[x];i;i=table[i].next)
if(table[i].to!=from)
DFS(table[i].to,x,dpt+1);
}
int main()
{
int i,j,x,y;
cin>>n;
for(i=1;i
