加快网站访问速度,男朋友说是做竞彩网站维护的,怎样自己制作app软件卖货,流媒体网站开发pdf正题
题目链接:https://www.luogu.com.cn/problem/P5904 题目大意 nnn个点的一棵树#xff0c;求有多少个点对(i,j,k)(i,j,k)(i,j,k)使得这三个点距离相等。 解题思路
有两种情况#xff0c;一是iii是j,kj,kj,k的祖先#xff0c;二是i,j,ki,j,ki,j,k互相没有祖先关系
考虑…正题
题目链接:https://www.luogu.com.cn/problem/P5904 题目大意
nnn个点的一棵树求有多少个点对(i,j,k)(i,j,k)(i,j,k)使得这三个点距离相等。 解题思路
有两种情况一是iii是j,kj,kj,k的祖先二是i,j,ki,j,ki,j,k互相没有祖先关系
考虑dpdpdpfi,jf_{i,j}fi,j表示iii点的子树中与iii距离为jjj的点的个数然后gi,jg_{i,j}gi,j表示iii的子树中满足有多少个点(x,y)(x,y)(x,y)对使得dis(x,lca)dis(y,lca)dis(i,lca)jdis(x,lca)dis(y,lca)dis(i,lca)jdis(x,lca)dis(y,lca)dis(i,lca)j。然后考虑统计答案 ansgy,i∗fx,i−1gx,i1∗fy,iansg_{y,i}*f_{x,i-1}g_{x,i1}*f_{y,i}ansgy,i∗fx,i−1gx,i1∗fy,i 然后考虑这个点对ggg的影响有 gx,i1fx,i1∗fy,ig_{x,i1}f_{x,i1}*f_{y,i}gx,i1fx,i1∗fy,i 然后继承gx,i−1gy,i,fx,i1fy,ig_{x,i-1}g_{y,i},f_{x,i1}f_{y,i}gx,i−1gy,i,fx,i1fy,i
然后可以长链剖分进行优化fff在长链上向后运动但是ggg是向前运动的。
考虑结点111因为每次向前运动要放在len1len_1len1的位置但是该位置向后又要储存len1len_1len1个值所以我们要开两倍的空间
时间复杂度O(n)O(n)O(n) codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N4e510;
struct node{ll to,next;
}a[N*2];
ll n,tot,ans,ls[N],son[N];
ll len[N],buff[N*2],bufg[N*2];
ll *f[N*2],*g[N*2],*nowf,*nowg;
void addl(ll x,ll y){a[tot].toy;a[tot].nextls[x];ls[x]tot;return;
}
void dfs(ll x,ll fa){for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa)continue;dfs(y,x);if(len[y]len[son[x]])son[x]y;}len[x]len[son[x]]1;return;
}
void solve(ll x,ll fa){f[x][0]1;if(son[x]){f[son[x]]f[x]1;g[son[x]]g[x]-1;solve(son[x],x);}ansg[x][0];for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yson[x]||yfa)continue;f[y]nowf;nowflen[y];nowglen[y]*210;g[y]nowg;solve(y,x);for(ll j0;jlen[y];j){if(j)ansg[y][j]*f[x][j-1];ansg[x][j1]*f[y][j];}for(ll j0;jlen[y];j){g[x][j1]f[y][j]*f[x][j1];if(j)g[x][j-1]g[y][j];f[x][j1]f[y][j];}}return;
}
int main()
{scanf(%lld,n);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}dfs(1,1);nowfbuff;nowgbufg;nowflen[1];nowglen[1]*210;f[1]buff;g[1]nowg;solve(1,1);printf(%lld,ans);
}
