[POI 21 Stage 1] Hotels

作法：

題目要在樹上找三個點，使得兩兩的距離一樣。那麼先考慮隨便選兩個點 A 和 B ，則 A 走到第三個點 C 的走法一定會是：先經過一段與 A 走到 B 的路徑重合的路徑，然後走到路徑上與AB等距的點的時候分岔出去。這裡就可以發現到，分岔的那個點對一個可行的三元組( A , B , C ) 會是唯一的，所以如果考慮枚舉分岔的那個點 P，就變成需要找所有到 P 等距的三元組，但三個點兩兩不能在 P 的同一子樹裡，否則會違反前面那個 A 走到 C 的走法。

所以枚舉 n 個點當根，還有對每個距離 D 都算一次。假設 P 的每個子樹裡和 P 距離為 D 的點個數分別是 x_1 , x_2 , ... , x_r ，那麼我們要求的就是 sum_( 1 <= i < j < k <= r ) x_i * x_j * x_k ，但我們能算的只有 sum ( x_i ) ,  sum ( x_i ^2 ) ,  sum ( x_i ^3 ) , 而用這三個東西就可以算出所求的答案。

實作上我是開一個 d[ 5000 ][ 5000 ] ， 在作以 P 為分岔點的時候，考慮他的子節點 S1 ~ Sr 們，並且先忽視他們連到 P 的邊，去算這些子樹中到 Si 的距離為 x 的點有幾個，記為 d[ Si ][ x ]，然後再枚舉到根的距離 D 。但如果直接從 0 枚舉到 n - 1 的話會沒辦法滿分 ，因為其實後面有很多 D 是全部都 0 個的，所以可以多紀錄一個子樹們的最大深度，只要讓 D 枚舉到那個深度就可以了。

code :

#include<bits/stdc++.h>
#define LL long long
#define SQR(x) (((LL)(x))*((LL)(x)))
#define CUB(x) (((LL)(x))*((LL)(x))*((LL)(x)))
using namespace std;
const int maxn=5000+10 ;
 
vector<int> v[maxn] ;
short d[maxn][maxn] ;
 
int n,root ;
int dfs(int x,int l,int f)
{
    d[root][l]++ ;
    int ret=l ;
    for(int i=0;i<v[x].size();i++) if(v[x][i]!=f)
        ret=max(ret,dfs(v[x][i],l+1,x)) ;
    return ret ;
}
 
int getd(int x,int f)
{
    fill(d[x],d[x]+n,0) ;
    root=x ;
    return dfs(x,0,f) ;
}
 
main()
{
    scanf("%d",&n) ;
    for(int i=1;i<n;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
 
    LL ans=0LL ;
    for(int i=1;i<=n;i++)
    {
        int maxd=0 ;
        for(int j=0;j<v[i].size();j++) maxd=max(maxd,getd(v[i][j],i)) ;
        for(int dep=0;dep<=maxd;dep++)
        {
            LL sum=0LL , sqr=0LL , cub=0LL ;
            for(int j=0;j<v[i].size();j++)
                sum+=d[v[i][j]][dep] ,
                sqr+=SQR(d[v[i][j]][dep]) ,
                cub+=CUB(d[v[i][j]][dep]) ;
            ans+=(CUB(sum)+2*cub-3*sqr*sum)/6 ;
        }
    }
    printf("%lld\n",ans) ;
}