【笔记】长链剖分

Author Avatar
Sakits 5月 06, 2018

简介

  长链剖分顾名思义和重链剖分不同之处就在于最深的儿子为重儿子。

性质

  一个点的kk级祖先所在的重链长度至少为kk
  证明:如果这个点和kk祖先在同一条重链上显然可得,如果不在同一条重链上那么一定在更长的链上。

应用1:求kk祖先

  先倍增,求出一个点的2n2^n倍祖先。
  长链剖分,记录链顶,并记录链顶向上向下链长个数个点,显然是O(n)O(n)的。
  预处理highbitxhighbit_x表示xx最高位的11
  设r=highbitkr=highbit_k,查询的时候先跳到2r2^{r}倍祖先,因为k2r<2rk-2^r<2^r,这个祖先的链顶一定有记录这个祖先的k2rk-2^r祖先是哪个,故可O(1)O(1)得到。

应用2:O(n)O(n)合并子树深度信息

  和dsu on tree 一样的思想,重儿子直接继承,轻儿子遍历,一条重链只会被遍历一次,故复杂度为O(n)O(n)
  一般来说是优化设fi,jf_{i,j}表示第ii个点,深度为jj的某种信息。
  继承重儿子的时候,深度实际上会整体+1+1,所以对于一个点xx,实际上是新增了一个fx,0f_{x,0},后面接上重儿子的一段,所以我们可以预处理一下下标。

inline void prepare(int x, int fa)
{
	pos[x]=++tott;
	if(son[x]) prepare(son[x], x);
	for(int i=last[x], too;i;i=e[i].pre)
	if((too=e[i].too)!=fa && too!=son[x]) prepare(too, x);
}

  按上方这么预处理下标,重儿子就刚好是连在xx的后面了,相当于接了上去继承。

例题

1.秘术

  分数规划,二分答案,求aibi<mid\frac{a_i}{b_i}<mid是否成立等价于判aibi×mid<0a_i-b_i\times mid<0,于是问题变成求长度为nn的最小权值链。
  先考虑暴力DP。设fi,jf_{i,j}为节点为ii向下长度为jj的最小权值。
  转移就随便转了。。继承的时候需要给整条重链加上xx的点权,可以用一个tagxtag_x来打标记。对于fxf_x定为tagsonx-tag_{son_x},然后把tagxtag_x加上tagsonxtag_{son_x}就能保证fxf_x只为xx的点权,而重链上其他点都加上xx的点权了。

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm>
#define ll long long 
using namespace std;
const int maxn=500010, inf=1e9;
const double eps=1e-6;
struct edge{int too, pre;}e[maxn<<1];
int n, m, x, y, tot, tott;
int a[maxn], b[maxn], last[maxn], dep[maxn], mxdep[maxn], son[maxn], pos[maxn];
double ans, tmp;
double c[maxn], f[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

inline void add(int x, int y){e[++tot]=(edge){y, last[x]}; last[x]=tot;}

void dfs1(int x, int fa)
{
	for(int i=last[x], too;i;i=e[i].pre)
	if((too=e[i].too)!=fa)
	{
		mxdep[too]=dep[too]=dep[x]+1;
		dfs1(too, x);
		mxdep[x]=max(mxdep[x], mxdep[too]);
		if(mxdep[too]>mxdep[son[x]]) son[x]=too;
	}
}

inline void dp(int x, int fa)
{
	pos[x]=++tott; 
	if(son[x]) dp(son[x], x);
	f[pos[x]]=-c[son[x]]; c[x]+=c[son[x]];
	for(int i=last[x], too;i;i=e[i].pre)
	if((too=e[i].too)!=fa && too!=son[x])
	{
		dp(too, x);		
		for(int j=1;j<=mxdep[too]-dep[x];j++)
		if(0<=m-1-j && m-1-j<=mxdep[x]-dep[x]) 
		ans=min(ans, f[pos[x]+m-1-j]+c[x]+f[pos[too]+j-1]+c[too]);
		for(int j=1;j<=mxdep[too]-dep[x];j++)
		f[pos[x]+j]=min(f[pos[x]+j], f[pos[too]+j-1]+c[too]+(a[x]-b[x]*tmp)-c[x]);
	}
	if(mxdep[x]-dep[x]+1>=m) ans=min(ans, f[pos[x]+m-1]+c[x]);
}

inline bool check(double mid)
{
	tmp=mid;
	for(int i=1;i<=n;i++) c[i]=a[i]-b[i]*mid;
	ans=1e18; for(int i=1;i<=n;i++) f[i]=1e18;
	tott=0; dp(1, 0);
	return ans<eps;
}

int main()
{
	freopen("cdcq_b.in", "r", stdin);
	freopen("cdcq_b.out", "w", stdout);
	read(n); read(m);
	for(int i=1;i<=n;i++) read(a[i]);
	for(int i=1;i<=n;i++) read(b[i]);
	if(m==-1)
	{
		double ans=1e18;
		for(int i=1;i<=n;i++) ans=min(ans, 1.0*a[i]/b[i]);
		return printf("%.2lf\n", ans), 0;
	}
	for(int i=1;i<n;i++) read(x), read(y), add(x, y), add(y, x);
	dfs1(1, 0); 
	double l=0, r=3e5;
	while(r-l>eps)
	{
		double mid=(r+l)/2;
		if(check(mid)) r=mid;
		else l=mid;
	}
	if(l>200000) return puts("-1"), 0;
	printf("%.2lf\n", l);
}

bzoj4543: [POI2014]Hotel加强版

  还是先考虑暴力DP。
  设fi,jf_{i,j}表示第ii个点的子树里,深度为jj的点有几个,gi,jg_{i,j}表示第ii个点的子树里,还差jj的距离的点就能凑成合法三元组的点对个数。
  需要注意的是gg继承的时候是深度1-1,所以继承重儿子的时候应该是整体左移,所以prepare完pos要倒过来。并且在转移的时候一个点的jj的值域还是+链长,而链顶是重链中下标最大的,所以可能出现链顶加完链长之后跑到其他点去了,故prepare的时候要在给链顶赋值下标前留一段长度为链长的空。

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm>
#define ll long long 
using namespace std;
const int maxn=500010, inf=1e9;
struct edge{int too, pre;}e[maxn<<1];
int n, x, y, tot, tott, tott2;
int last[maxn], dep[maxn], mxdep[maxn], son[maxn], f[maxn], ffpos[maxn], gpos[maxn], top[maxn];
ll ans, g[maxn];

template<typename T>
inline void read(T &k)
{
	int f=1; k=0; char c=getchar();
	while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
	while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
	k*=f;
}

inline void add(int x, int y){e[++tot]=(edge){y, last[x]}; last[x]=tot;}

void dfs(int x, int fa)
{
	for(int i=last[x], too;i;i=e[i].pre)
	if((too=e[i].too)!=fa)
	{
		mxdep[too]=dep[too]=dep[x]+1;
		dfs(too, x);
		mxdep[x]=max(mxdep[x], mxdep[too]);
		if(mxdep[too]>mxdep[son[x]]) son[x]=too;
	}
}

void dfs2(int x, int fa, int tp)
{
	top[x]=tp; 
	if(son[x]) dfs2(son[x], x, tp);
	for(int i=last[x], too;i;i=e[i].pre)
	if((too=e[i].too)!=fa && too!=son[x]) dfs2(too, x, too);
}

inline void prepare(int x, int fa)
{
	if(top[x]==x) tott2+=mxdep[top[x]]-dep[top[x]];
	ffpos[x]=++tott; gpos[x]=++tott2; gpos[x]=(n<<1)-gpos[x]+1;
	if(son[x]) prepare(son[x], x);
	for(int i=last[x], too;i;i=e[i].pre)
	if((too=e[i].too)!=fa && too!=son[x]) prepare(too, x);
}

void dp(int x, int fa)
{
	if(son[x]) dp(son[x], x);
	f[ffpos[x]]=1;
	for(int i=last[x], too;i;i=e[i].pre)
	if((too=e[i].too)!=fa && too!=son[x])
	{
		dp(too, x);
		for(int j=1;j<=mxdep[too]-dep[x];j++) 
		ans+=1ll*f[ffpos[too]+j-1]*g[gpos[x]+j];
		for(int j=1;j<=mxdep[too]-dep[too];j++) 
		ans+=1ll*f[ffpos[x]+j-1]*g[gpos[too]+j];
		for(int j=1;j+1<=mxdep[too]-dep[too];j++) g[gpos[x]+j]+=g[gpos[too]+j+1]; 
		for(int j=1;j<=mxdep[too]-dep[x];j++)
		g[gpos[x]+j]+=1ll*f[ffpos[x]+j]*f[ffpos[too]+j-1];
		for(int j=1;j<=mxdep[too]-dep[x];j++) 
		f[ffpos[x]+j]+=f[ffpos[too]+j-1];
	}
	ans+=g[gpos[x]];
}

int main()
{
	read(n);
	for(int i=1;i<n;i++) read(x), read(y), add(x, y), add(y, x);
	dfs(1, 0); dfs2(1, 1, 1); prepare(1, 0); dp(1, 0);
	printf("%lld\n", ans);
}