bzoj 4543 Hotel加强版

Posted on | Views:

长链剖分经典题目.

设 $f(i,j)$ 表示子树 $i$ 中距离 $i$ 为 $j$ 的点的数目.

设 $g(i,j)$ 表示子树 $i$ 中点对 $(x,y)$ 的数目,其中点对满足 $x,y$ 的 $lca$ 与它们的距离都为 $d$ ,而与 $i$ 的距离为 $d-j$ .

借用一下 $\text{Bill Yang}$ 的图片.

直接暴力合并 $u$ 与它的儿子节点 $v$ 的信息,时间复杂度是 $O(n^2)$ 的,只能通过原题.

注意到维护的下标是以深度为下标,利用长链剖分即可做到 $O(n)$ .

合并 $u$ 当前信息与它的儿子 $v​$ 的信息时,转移有,
$$
ans+=f(u,j-1)\cdot g(v,j)+g(u,j+1)\cdot f(v,j) \\
g(u,j+1)+=f(u,j+1)\cdot f(v,j)\\
g(u,j)+=g(v,j+1) \\
f(u,j)+=f(v,j-1)
$$
利用指针移动实现空间的高效分配,以及继承重儿子信息.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		fh=-1,jp=getchar();
	while (jp>='0'&&jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*fh;
}
const int MAXN=1e5+10;
int n,ecnt=0,nx[MAXN<<1],to[MAXN<<1],head[MAXN];
void addedge(int u,int v)
{
	++ecnt;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
int mxdep[MAXN],mxson[MAXN];
void dfs_init(int u,int fa)
{
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==fa)
			continue;
		dfs_init(v,u);
		mxdep[u]=max(mxdep[u],mxdep[v]);
		if(!mxson[u] || mxdep[v]>mxdep[mxson[u]])
			mxson[u]=v;
	}
	mxdep[u]=mxdep[mxson[u]]+1;
}
ll *f[MAXN],*g[MAXN],tmp[MAXN<<2],*id=tmp,ans=0;
void dfs(int u,int fa)
{
	if(mxson[u])
	{
		f[mxson[u]]=f[u]+1;
		g[mxson[u]]=g[u]-1;
		dfs(mxson[u],u);
	}
	f[u][0]=1;
	ans+=g[u][0];
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(v==fa || v==mxson[u])
			continue;
		f[v]=id,id+=mxdep[v]<<1,g[v]=id,id+=mxdep[v]<<1;
		dfs(v,u);
		for(int j=0;j<mxdep[v];++j)
		{
			if(j)
				ans+=f[u][j-1]*g[v][j];
			ans+=g[u][j+1]*f[v][j];
		}
		for(int j=0;j<mxdep[v];++j)
		{
			g[u][j+1]+=f[u][j+1]*f[v][j];
			if(j)
				g[u][j-1]+=g[v][j];
			f[u][j+1]+=f[v][j];
		}
	}
}
int main()
{
	n=read();
	for(int i=1;i<n;++i)
	{
		int u=read(),v=read();
		addedge(u,v);
		addedge(v,u);
	}
	dfs_init(1,0);
	f[1]=id,id+=mxdep[1]<<1,g[1]=id,id+=mxdep[1]<<1;
	dfs(1,0);
	cout<<ans<<endl;
	return 0;
}