题目概述

给出一棵树，求多少个 $(a,b,c),a<b<c$ 满足三个点两两距离相同。

解题报告

考虑以这三个点的LCA $x$ 统计答案，则只有两种情况：

1. 在 $x$ 不同儿子 $u,v$ 中，$u$ 子树中选出两个点 $a,b$ ，满足到 $LCA(a,b)$ 距离为 $d$ ，且 $LCA(a,b)$ 到 $x$ 距离为 $k$ ，然后从 $v$ 子树中选出一个点 $c$ ，到 $x$ 距离为 $d-k$ 。
2. 在 $x$ 子树中选出两个点 $a,b$ ，满足到 $LCA(a,b)$ 距离为 $d$ ，且 $LCA(a,b)$ 到 $x$ 距离为 $d$ 。

因此可以想到这么DP：定义 $f_{i,j}$ 表示 $i$ 子树到 $i$ 距离为 $j$ 的个数，$g_{i,j}$ 表示 $i$ 子树中选出两个点 $a,b$ ，到 $LCA(a,b)$ 距离为 $d$ ，且 $LCA(a,b)$ 到 $i$ 距离为 $d-j$ 的方案数。

然后上面两种情况就分别对应：

1. $g_{u,i}f_{x,i-1}[i>1]+g_{x,i+1}f_{u,i}$ ，其中 $f_{x,i}$ 记录的是前面处理的儿子的总和，前面需要 $i>1$ 是避免和第二种数重。
2. $g_{x,0}$ ，$g_{x,0}$ 表示处理完 $x$ 子树后的值。

由于和距离有关，因此可以用长链剖分优化DP，其中 $g$ 数组由于定义是 $d-j$ ，因此是往左移的，需要多开空间。

示例程序

#include<cstdio>
#include<cctype>
using namespace std;
typedef long long LL;
const int maxn=100000;

int n,dep[maxn+5],md[maxn+5],SH[maxn+5],len[maxn+5];
int E,lnk[maxn+5],nxt[(maxn<<1)+5],to[(maxn<<1)+5];
LL tem[maxn*3+5],*pl=tem,*f[maxn+5],*g[maxn+5],ans;

#define EOLN(x) ((x)==10 || (x)==13 || (x)==EOF)
inline char readc(){
    static char buf[1<<16],*l=buf,*r=buf;
    return l==r && (r=(l=buf)+fread(buf,1,1<<16,stdin),l==r)?EOF:*l++;
}
template<typename T> int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    lst=='-'?x=-tot:x=tot;return EOLN(ch);
}
inline void Add(int x,int y) {to[++E]=y;nxt[E]=lnk[x];lnk[x]=E;}
void DFS(int x,int pre=0){
    dep[x]=dep[pre]+1;md[x]=dep[x];
    for (int j=lnk[x];j;j=nxt[j])
        if (to[j]!=pre){
            DFS(to[j],x);
            if (md[to[j]]>md[x]) md[x]=md[to[j]],SH[x]=to[j];
        }
    len[x]=len[SH[x]]+1;
}
void DP(int x,int pre=0,bool fl=true){
    if (fl) f[x]=pl,pl+=len[x],g[x]=pl+len[x]-1,pl+=len[x]<<1;
    f[x][0]=1;
    if (SH[x]) f[SH[x]]=f[x]+1,g[SH[x]]=g[x]-1,DP(SH[x],x,false);
    for (int j=lnk[x],u;j;j=nxt[j])
        if ((u=to[j])!=pre && u!=SH[x]){
            DP(u,x,true);
            for (int j=0;j<len[u];j++){
                ans+=f[u][j]*g[x][j+1];
                if (j>1) ans+=f[x][j-1]*g[u][j];
            }
            for (int j=0;j<len[u];j++){
                g[x][j+1]+=f[x][j+1]*f[u][j];
                f[x][j+1]+=f[u][j];
                if (j) g[x][j-1]+=g[u][j];
            }
        }
    ans+=g[x][0];
}
int main(){
    readi(n);
    for (int i=1,x,y;i<n;i++) readi(x),readi(y),Add(x,y),Add(y,x);
    DFS(1);DP(1);
    printf("%lld\n",ans);
    return 0;
}