题意

有一个树形结构的宾馆，n个房间，n-1条无向边，每条边的长度相同，任意两个房间可以相互到达。吉丽要给他的三个妹子各开（一个）房（间）。三个妹子住的房间要互不相同（否则要打起来了），为了让吉丽满意，你需要让三个房间两两距离相同。
有多少种方案能让吉丽满意？
n<=100000

前言

这篇博客一直没有写，是因为我想把他拿来复习
所以拖了很多天
感觉复习效果还是不错的吧
大部分都记得

题解

考虑DP
f[i][j]表示以i为根的子树，与点$i$距离为$j$的有多少个
g[i][j]表示以i为根的子树，有多少个点对满足他们到LCA的距离为d，然后LCA到i的距离为$d-j$。换句话说，就是不在i子树里面的一个点o，如果他和i的距离为j，那么他就可以和这个点对组成三元组
然后可以得到DP递推式
下面$y$是$i$的一个儿子
$f[i][j]+=f[y][j-1]$
$g[i][j]+=g[y][j+1]$
$gi][j]+=f[i][j]*f[y][j-1]$
$ans+=f[i][j]*g[y][j+1]+g[x][j]*f[y][j-1]$
但是这样时空都会爆
转移的复杂度是y的最深深度
因为，我们知道，对于x，他遍历的第一个儿子，f和g数组的信息基本上是一样的
只需要稍微偏移一点就可以完全复制
于是我们考虑长链剖分
每一次选择深度最深的儿子，直接复制他的信息
这个过程可以用指针来优化

时间复杂度:
设转移复杂度为$t$，每个点的最深深度为$dep[i]$

CODE:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long LL;
const LL N=100005*2;
struct qq {LL x,y,last; }e[N];LL num,last[N];
LL n;
void init (LL x,LL y)
{num++;e[num].x=x;e[num].y=y;e[num].last=last[x];last[x]=num;
}
LL ff[N];
LL md[N],son[N];
LL T[1000010];
LL *f[N],*g[N],*now=T+1;
void Dfs (LL x)
{md[x]=1;for (LL u=last[x];u!=-1;u=e[u].last){LL y=e[u].y;if (y==ff[x]) continue;ff[y]=x;Dfs(y);md[x]=max(md[x],md[y]+1);if (md[y]>md[son[x]]) son[x]=y;}
}
LL ans=0;
void dfs (LL x)
{if (son[x]!=0){f[son[x]]=f[x]+1;g[son[x]]=g[x]-1;dfs(son[x]);}f[x][0]=1;ans=ans+g[x][0];for (LL u=last[x];u!=-1;u=e[u].last){LL y=e[u].y;if (y==son[x]||y==ff[x]) continue;f[y]=now;now=now+md[y];g[y]=now+md[y];now=now+md[y]*2;dfs(y);for (LL i=md[y]-1;i>=0;i--){if (i!=0) ans=ans+f[x][i-1]*g[y][i];ans=ans+g[x][i+1]*f[y][i];  //printf("x:%lld y:%lld %lld %lld\n",x,y,f[x][i-1]*g[y][i],g[x][i+1]*f[y][i]);g[x][i+1]=g[x][i+1]+f[x][i+1]*f[y][i];}for (LL i=0;i<md[y];i++){if (i!=0) g[x][i-1]+=g[y][i];f[x][i+1]+=f[y][i];}}}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%lld",&n);for (LL u=1;u<n;u++){LL x,y;scanf("%lld%lld",&x,&y);init(x,y);init(y,x);}Dfs(1);f[1]=now;now=now+md[1];g[1]=now+md[1];now=now+md[1]*2;dfs(1); printf("%lld\n",ans);return 0;
}