You have to learn what you don't understand!

brief introduction

The difference between it and light chain dissection is that the definition of heavy son has changed from the largest son in the subtree to the deepest son in the subtree.

So we can know that it is mainly used to solve problems related to depth. It is widely used in optimization \ (dp \), but it is very flexible, so we must practice.

nature

Nature 1

The length of \ (o) and (n) of all chains.

Property 2

The length of the long chain of \ (k \) secondary ancestor \ (y \) of any point is greater than or equal to \ (k \)

Property 3

The number of times any point jumps over the heavy chain will not exceed \ (\ sqrt n \) times

Don't bother to prove that the above properties are more obvious than one \ (... \)

application

1, Calculate the k-th ancestor

This must be highly recommended This giant The solution to the problem has made me understand!

Preprocess these things first:

• Split the long chain of the tree and record the chain head and depth of each point, \ (O(n) \)
• Multiply the \ (2^n \) secondary ancestors of each point, \ (O(n\log n) \)
• If the length of a chain is \ (len \), record the up \ (len \) ancestors and down \ (len \) chain elements of the chain head, \ (O(n) \)
• Record the binary highest bit of each number \ (1 \), \ (O(n) \)

The algorithm process is as follows:

• First jump the highest bit of \ (K \) by using the multiplication array, and set the remaining steps as \ (k '\), then the number of steps jumped by \ (k' < \ frac{k}{2} < \)
• According to the conclusion: if the length of the long chain of the k-th ancestor y of any point is greater than or equal to K, the length of the long chain of the current point must be \ (\ geq \) the number of steps \ (> k '\), and then the \ (k \) ancestor can be obtained with the preprocessed up or down array \ (O(1) \).

The complexity bottleneck is preprocessing \ (O(n\log n) \), but only \ (O(1) \) is required for a single query

2, Optimized dp

In combination with this example: Hotels

First consider the positional relationship of these three points. We consider that the answer may be like this. The answers of the questions on the tree can be counted at \ (lca \):

Then use \ (dp \) to count these situations. Let \ (f(i,j) \) represent the number of \ (j \) points with depth within \ (i \) subtree, and \ (g(i,j) \) represent the number of unordered number pairs \ ((i,j) \) satisfying \ (d(lca(x,y),x)=d(lca(x,y),y)=d(lca(x,y),i)+j \) within \ (i \) subtree. Then the answer is as follows:

• \(ans\leftarrow g(i,0) \), corresponding to the second case.

• \(ans\leftarrow \sum_{x\not=y} f(x,j-1)g(y,j+1)\)

I think it should be transferred in this way. According to the definition:

• \(g(i,j)\leftarrow \sum_{x<y} f(x,j-1)f(y,j-1)\)
• \(g(i,j)\leftarrow\sum g(x,j+1)\)
• \(f(i,j)\leftarrow\sum f(i,j-1)\)

Violence transfer is \ (O(n^2) \), but it is found that the subscripts are only related to depth, so it can be optimized by long chain partition. Complexity proves to be very ingenious. Since we directly inherit the \ (dp \) value of heavy son and join light son violently, the complexity consumption is the depth of light chain. Since each chain will be added only once, according to the nature \ (1 \) total chain length \ (O(n) \), then the time complexity \ (O(n) \)

A difficulty in writing long chain subdivision is to inherit the information of the heavy son. It needs to be maintained with a pointer. Just divide a large array with a pointer. In order to prevent \ (\ tt RE \), you can arrange more space.

But there's a little thing I haven't learned yet!

#include <cstdio>
const int M = 100005;
#define int long long
int read()
{
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
	while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,tot,F[M],d[M],dep[M],son[M];
int *f[M],*g[M],p[4*M],*o=p,ans;
struct edge
{
	int v,next;
	edge(int V=0,int N=0) : v(V) , next(N) {}
}e[2*M];
void pre(int u,int fa)
{
	d[u]=d[fa]+1;
	for(int i=F[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa) continue;
		pre(v,u);
		if(dep[v]>dep[son[u]]) son[u]=v;
	}
	dep[u]=dep[son[u]]+1;
}
void dfs(int u,int fa)
{
	if(son[u])//Visit your son first
	{
		f[son[u]]=f[u]+1,g[son[u]]=g[u]-1;
		dfs(son[u],u);
	}
	f[u][0]=1;
	ans+=g[u][0];//Didn't learn to understand
	for(int i=F[u];i;i=e[i].next)
	{
		int v=e[i].v;
		if(v==fa || v==son[u]) continue;
		f[v]=o;o+=dep[v]*2;g[v]=o;o+=dep[v]*2;
		dfs(v,u);
		for(int j=0;j<dep[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<dep[v];j++)
		{
			g[u][j+1]+=f[v][j]*f[u][j+1];
			if(j) g[u][j-1]+=g[v][j];
			f[u][j+1]+=f[v][j];
		}
	}
}
signed main()
{
	n=read();
	for(int i=1;i<n;i++)
	{
		int u=read(),v=read();
		e[++tot]=edge(v,F[u]),F[u]=tot;
		e[++tot]=edge(u,F[v]),F[v]=tot;
	}
	pre(1,0);
	f[1]=o;o+=dep[1]*2;g[1]=o;o+=dep[1]*2;
	dfs(1,0);
	printf("%lld\n",ans);
}

3, Strange applications?

Read it again when you have time, \ (yyb \) on the blog

https://www.cnblogs.com/cjyyb/p/9479258.html