点分治复习笔记

1.Tree

Description:

求一棵树中长度不超过\(K\)的路径条数

Solution:

直接统计深度,由于深度的贡献具有单调性

考虑每次统计答案时先排序,然后双指针每次相减

这样就比\(n^2\)统计优秀多了,记得要减掉算重的

2.[模版]点分治1

Description:

求一棵树中是否存在长度为\(K\)的链,\(m\)组询问,\(m \le 100\)

Solution:

考虑每次用桶把路径长度标记,把所有询问在桶里查一遍,再清空桶

复杂度\(O(nmlog^2n)\)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=1e5+5,inf=1e7;
int n,m,s,rt,cnt,tot,sumsz,f[mxn],hd[mxn],sz[mxn],vis[mxn],dis[mxn],ask[mxn],ans[mxn],tag[mxn],dep[mxn],bac[inf+5];

inline int read() {
	char c=getchar(); int x=0,f=1;
	while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
	return x*f;
}
inline void chkmax(int &x,int y) {if(xy) x=y;}

struct ed {
	int to,nxt,w;
}t[mxn<<1];

inline void add(int u,int v,int w) {
	t[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt;
}

int getrt(int u,int fa) {
	sz[u]=1; f[u]=0;
	for(int i=hd[u];i;i=t[i].nxt) {
		int v=t[i].to;
		if(v==fa||vis[v]) continue ;
		getrt(v,u); sz[u]+=sz[v];
		chkmax(f[u],sz[v]);
	}
	chkmax(f[u],sumsz-sz[u]);
	if(f[u]ask[j]) break ;
				ans[j]|=bac[ask[j]-dis[k]];
			}
		}
		for(int k=1;k<=tot;++k) 
			if(dis[k]<=inf) bac[dis[k]]=1,tag[++s]=dis[k];
	}
	for(int i=1;i<=s;++i) bac[tag[i]]=0; bac[0]=1;
}

void solve(int u) {
	vis[u]=1; cal(u); 
	for(int i=hd[u];i;i=t[i].nxt) {
		int v=t[i].to;
		if(vis[v]) continue ;
		sumsz=sz[v]; rt=0; 
		getrt(v,u); solve(rt);
	}
}

int main()
{
	n=read(); m=read(); int u,v,w; bac[0]=1; 
	for(int i=1;i

3.聪聪可可

Description:

给你一棵树,询问有多少条路径满足边权和为3的倍数

Solution:

和Tree差不多......统计时开3个桶,乘法原理搞一下就行

4.Distance in Tree

Description:

给你一棵树,问路径长为K的条数

Solution:

方法同2,如果你无聊的话可以写个类似Tree的写法用<=k的减去

居然跑了rk5?

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=1e5+5;
int n,m,k,rt,cnt,tot,ans,sumsz,f[mxn],hd[mxn],sz[mxn],bac[mxn],dep[mxn],vis[mxn],dis[mxn];

inline int read() {
	char c=getchar(); int x=0,f=1;
	while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
	return x*f;
}
inline void chkmax(register int &x,register int y) {if(xy) x=y;}

struct ed {
	int to,nxt,w;
}t[mxn<<1];

inline void add(register int u,register int v,register int w) {
	t[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt;
}

int getrt(register int u,register int fa) {
	f[u]=0; sz[u]=1;
	for(register int i=hd[u];i;i=t[i].nxt) {
		register int v=t[i].to;
		if(v==fa||vis[v]) continue ;
		getrt(v,u); sz[u]+=sz[v];
		chkmax(f[u],sz[v]);
	}
	chkmax(f[u],sumsz-sz[u]);
	if(f[rt]>f[u]) rt=u;
}

void getdis(register int u,register int fa) {
	if(dep[u]<=k) ++dis[dep[u]],ans+=bac[k-dep[u]];
	for(register int i=hd[u];i;i=t[i].nxt) {
		register int v=t[i].to;
		if(v==fa||vis[v]) continue ;
		dep[v]=dep[u]+t[i].w; getdis(v,u); 
	}
}

void cal(register int u) {
	tot=0; 
	for(register int i=hd[u];i;i=t[i].nxt) {
		register int v=t[i].to;
		if(vis[v]) continue ;
		dep[v]=t[i].w; getdis(v,u);
		for(register int j=1;j<=k;++j) 
			bac[j]+=dis[j],dis[j]=0;
	}
	for(register int i=1;i<=k;++i) bac[i]=0;
}

void solve(register int u) {
	cal(u); vis[u]=1;
	for(register int i=hd[u];i;i=t[i].nxt) {
		register int v=t[i].to;
		if(vis[v]) continue ;
		rt=0; sumsz=sz[v];
		getrt(v,u); solve(rt);
	}
}

int main()
{
	n=read(); k=read(); register int u,v,w; bac[0]=1;
	for(register int i=1;i

5.[IOI2011] Race

Description:

求树上的一条路径,长度为K且边最少

Solution:

其实也很简单,就用Tree的方法直接计数,然后减去

不同的是,要把答案扔到一个边数桶里

6.树上游戏

Description:

lrb有一棵树，树的每个节点有个颜色。给一个长度为n的颜色序列，定义s(i,j) 为i 到j 的颜色数量。以及

现在他想让你求出所有的sum[i]

Solution:

毒瘤题,考虑第一次碰到一种颜色会产生该点子树的贡献

看代码吧:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=1e5+5;
int n,m,s,rt,cnt,sumsz,hd[mxn];
int f[mxn],val[mxn],sz[mxn],vis[mxn];
int num[mxn],fs[mxn],col[mxn],tot[mxn];
ll sum,ans[mxn];

inline int read() {
	char c=getchar(); int x=0,f=1;
	while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
	return x*f;
}
inline void chkmax(int &x,int y) {if(xy) x=y;}

struct ed {
	int to,nxt;
}t[mxn<<1];

inline void add(int u,int v) {
	t[++cnt]=(ed) {v,hd[u]}; hd[u]=cnt;
}

int getrt(int u,int fa) {
	sz[u]=1; f[u]=0;
	for(int i=hd[u];i;i=t[i].nxt) {
		int v=t[i].to;
		if(v==fa||vis[v]) continue ;
		getrt(v,u); sz[u]+=sz[v];
		chkmax(f[u],sz[v]);
	}
	chkmax(f[u],sumsz-sz[u]);
	if(f[u]

7.[BJOI2017]难题

Description:

每条边有颜色,路径的权值定义为连续颜色段权值的和,求一条长为[L,R]路径的最大权值

Solution:

本来可以直接开桶维护最大值

但是更新答案时要查询一段区间,很烦

考虑类似滑动窗口那题的单调队列优化

或者你也可以写个线段树合并

这题恶心的一点是你要考虑颜色相同时的合并

所以遍历儿子时要把相同颜色边的弄到一起,方便讨论

合并时注意还要按深度启发式合并,保证复杂度

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ls p<<1 
#define rs p<<1|1
using namespace std;
typedef long long ll;
const int mxn=1e5+5,inf=1e9;
int n,m,L,R,rt,ans,cnt,sumsz,hd[mxn];
int sz[mxn],mx[mxn],dep[mxn],vis[mxn],col[mxn],colmx[mxn],T[mxn],dis[mxn],f[mxn],g[mxn];

inline int read() {
	char c=getchar(); int x=0,f=1;
	while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}
	return x*f;
}
inline void chkmax(int &x,int y) {if(xy) x=y;}

struct ed {
	int to,nxt,w;
}t[mxn<<1];

inline void add(int u,int v,int w) {
	t[++cnt]=(ed) {v,hd[u],w}; hd[u]=cnt;
}

void getrt(int u,int fa) {
	mx[u]=0; sz[u]=1;
	for(int i=hd[u];i;i=t[i].nxt) {
		int v=t[i].to;
		if(v==fa||vis[v]) continue ;
		getrt(v,u); sz[u]+=sz[v];
		chkmax(mx[u],sz[v]);
	}
	chkmax(mx[u],sumsz-sz[u]);
	if(mx[rt]>mx[u]) rt=u;
}

void getdep(int u,int fa,int d) {
	dep[u]=d;
	for(int i=hd[u];i;i=t[i].nxt) {
		int v=t[i].to;
		if(v==fa||vis[v]) continue ;
		getdep(v,u,d+1); chkmax(dep[u],dep[v]);
	}
}

void getval(int u,int fa,int val,int las,int d) {
	if(d>R) return ;
	chkmax(dis[d],val);
	for(int i=hd[u];i;i=t[i].nxt) {
		int v=t[i].to;
		if(v==fa||vis[v]) continue ;
		getval(v,u,val+(t[i].w!=las)*col[t[i].w],t[i].w,d+1);
	}
}

struct Buc {
	int col,deep,id;
	friend bool operator < (Buc x,Buc y) {
		if(x.col==y.col) return x.deep=L) 
			if(flag) chkmax(res,a[q[h]]-val+b[i]);
			else b[i]=a[q[h]]; //处理T数组,表示在i+len在[L,R]的f[i]的max
	}
	return res;
}

void solve(int u) {
	vis[u]=1; int cnts=0;
	for(int i=hd[u];i;i=t[i].nxt) {
		int v=t[i].to;
		if(vis[v]) continue ;
		getdep(v,u,1); chkmax(colmx[t[i].w],dep[v]);
		A[++cnts]=(Buc){t[i].w,dep[v],v};
	}
	sort(A+1,A+cnts+1); //排序
	if(A[cnts].deep*2
点分治

相关

洛谷P2664 树上游戏——点分治

点分治 学习笔记

[LOJ#2386]. 「USACO 2018.01 Platinum」Cow at Large[点分治]

点分治 & 边分治

poj1741 Tree （点分治）

点分治

#树形依赖背包，点分治#BZOJ 4182 Shopping

点分治

标签

一品网 冀ICP备14022925号-6