动态点分治(点分树)学习笔记
|
881
|
0
|
学习笔记

650 字
|
3 分钟

前言

别问我为啥不和点分治写一块。。。内容过多了。。。所以分开写

正文

我们知道，在处理树上问题的时候，点分治是一个很好用的算法，但是倘若是多次询问或者是带修改操作，那么就需要重新点分治，这样的效率极其低下，那么我们就考虑重构这整棵树。把每个点与他的子树中的重心（或者假重心，可以看看我点分治那篇的最后update有提到）相连，也就是建father。然后再进行统计，不过这次的统计与点分治的统计有不同，点分治的统计相当于是找了个中间点，对于两个端点进行枚举匹配，而点分树则是已知一个端点，对于他的中间点与另一个端点进行枚举统计，可以参照下图片。

  • 这是点分治的查找方式，找重心为中心点然后利用两端统计
  • 这是点分树的查找方式，从一个点向上爪巴，并且用父亲节点(包含他的上级子树的重心)当中间点进行统计(注意这棵树已经不是原树，是点分树)

因为一个树按照重心构造他的高度不可能大于$logn$,所以树分治对一个点查询是$logn$的，统计全局就是$nlogn$的,所以如果你闲着无聊的话点分治也可以用点分树打。

然后考虑容斥，和点分治不同，你需要维护一个点子树内点到该点的路径信息和这个点内子树到该点father的路径信息，为什么？再看一张图。

如图，对于蓝点来说，这些红色的路径显然是不可行的，那么我们统计蓝色点的贡献时就用蓝色的点的子树内点到该点的合法贡献-橙色点内子树到该点father的合法贡献

由此我们就可以得出点分树的一般形式的板子了，然后修改的话一路从叶子$update$到根即可。

代码

以下是一些点分树的题目的代码：

bzoj3730震波

线段树被卡常了，过不去，悲。

#pragma G++ optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h> 
#define Maxn 100005
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
struct edge{int next,to;}e[Maxn<<1];
struct seg{int ls,rs,sum[2];}tree[8000005];
bool vis[Maxn];
int tmp,M[Maxn][20],father[Maxn],rt[Maxn],f[Maxn][25],head[Maxn],value[Maxn],root,Min,deep[Maxn],lastans=0,cnt=0,size[Maxn],n,m,tot=0;
struct FastIO
{
	static const int S=1048576;
	char buf[S],*L,*R;int stk[20],Top;
	~FastIO(){clear();}
	inline char nc(){return L==R&&(R=(L=buf)+fread(buf,1,S,stdin),L==R)?EOF:*L++;}
	inline void clear(){fwrite(buf,1,Top,stdout);Top=0;}
	inline void pc(char ch){Top==S&&(clear(),0);buf[Top++]=ch;}
	inline void endl(){pc('\n');}
	FastIO& operator >> (int& ret){ret=0;int f=1;char ch=nc();while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=nc();}while(ch>='0'&&ch<='9'){ret=ret*10+ch-'0';ch=nc();}ret*=f;return *this;}
	FastIO& operator >> (char* s){register int Len=0;register char ch=nc();while(ch!='\n'){*(s+Len)=ch;Len++;ch=nc();}}
	FastIO& operator << (int x){while(stk[++stk[0]]=x%10,x/=10);while(stk[0]) pc('0'+stk[stk[0]--]);return *this;}
	FastIO& operator << (char ch){pc(ch);return *this;}
	FastIO& operator << (string str){register int Len=str.size()-1;for(stk[0]=0;Len>=0;Len--) stk[++stk[0]]=str[Len];while(stk[0]) pc(stk[stk[0]--]);return *this;}
}fin,fout;
inline void add(int a,int b){e[++cnt].next=head[a];e[cnt].to=b;head[a]=cnt;}
inline void Get_rt(int now,int fa,int Size)
{
	int Max_size=0;size[now]=1;
	for (int i=head[now],v;i;i=e[i].next) (v=e[i].to)^fa&&!vis[v]&&
		(Get_rt(v,now,Size),size[now]+=size[v],Max_size=max(Max_size,size[v])); 
	Max_size=max(Max_size,Size-size[now]),Max_size<Min&&(Min=Max_size,root=now);
}
inline void dfs(int now,int fa)
{
	f[now][0]=fa,deep[now]=deep[fa]+1;
	for (int i=1;i<=16;i++) f[now][i]=f[f[now][i-1]][i-1];
	for (int i=head[now],v;i;i=e[i].next) (v=e[i].to)^fa&&(dfs(v,now),0);
}
inline int LCA(int x,int y)
{
	if (deep[x]<=deep[y]) swap(x,y);
	for (int i=16;~i;--i)
	{
		deep[f[x][i]]>=deep[y]&&(x=f[x][i]);
		if (x==y) return x;
	}
	for (int i=16;~i;--i) f[x][i]^f[y][i]&&(x=f[x][i],y=f[y][i]);
	return f[x][0];
}
inline int getdis(int x,int y){return deep[x]+deep[y]-2*deep[LCA(x,y)];}
inline void Build_up(int now,int fa)
{
	father[now]=fa;vis[now]=1;
	for (int i=head[now],v;i;i=e[i].next)
		!vis[v=e[i].to]&&(v=e[i].to)^fa&&(Min=2e9,Get_rt(v,v,size[v]),Build_up(root,now),0);
}
inline void update(int &Root,int l,int r,int wz,int x,int opt)
{
	if (!Root) Root=++tot; 
	if (l==r&&l==wz) {tree[Root].sum[opt]+=x;return;}
	int mid=l+r>>1;
	if (wz<=mid) update(tree[Root].ls,l,mid,wz,x,opt);
	else update(tree[Root].rs,mid+1,r,wz,x,opt);
	tree[Root].sum[opt]=tree[tree[Root].ls].sum[opt]+tree[tree[Root].rs].sum[opt];
} 
inline int query(int Root,int l,int r,int ql,int qr,int opt)
{
	if (l==ql&&r==qr) return tree[Root].sum[opt];
	int mid=l+r>>1;
	if (qr<=mid) return query(tree[Root].ls,l,mid,ql,qr,opt);
	if (ql>mid) return query(tree[Root].rs,mid+1,r,ql,qr,opt);
	if (ql<=mid&&mid<qr) return query(tree[Root].ls,l,mid,ql,mid,opt)+query(tree[Root].rs,mid+1,r,mid+1,qr,opt);	
}
inline int get_ans(int now,int len)
{
	tmp=0;
	int ans=query(rt[now],0,n,0,len,1);
	for (int u=now,dis;father[u];u=father[u])
		(dis=len-M[now][tmp++])>=0&&(ans+=query(rt[father[u]],0,n,0,dis,1)-query(rt[u],0,n,0,dis,0));
	return ans;
}
inline void change(int now,int val)
{
	tmp=0,update(rt[now],0,n,0,val-value[now],1);
	for (int u=now,dis;father[u];u=father[u]) dis=M[now][tmp++],
		update(rt[father[u]],0,n,dis,val-value[now],1),
		update(rt[u],0,n,dis,val-value[now],0);
	value[now]=val;
}
int main()
{
	register int i,u,v,dis; fin>>n>>m;
	for (i=1;i<=n;++i) fin>>value[i];
	for (i=1;i<n;++i) fin>>u>>v,add(u,v),add(v,u);
	Min=2e9,dfs(1,0),Get_rt(1,1,n);
	int sx=root;
	for (Build_up(root,0),i=1;i<=n;i++)
		for (update(rt[i],0,n,0,value[i],1),tmp=0,u=i;father[u];u=father[u])
			M[i][tmp++]=dis=getdis(i,father[u]),
			update(rt[u],0,n,dis,value[i],0),update(rt[father[u]],0,n,dis,value[i],1);
	int x,y,opt;while (m--) fin>>opt>>x>>y,x^=lastans,y^=lastans,
		!opt?(lastans=get_ans(x,y),fout<<lastans,fout.endl(),0):(change(x,y),0); 
	return 0;
}
/*
8 1
1 10 100 1000 10000 100000 1000000 10000000
1 2
1 3
2 4
2 5
3 6
3 7
3 8
0 3 1
*/

bzoj2117[2010国家集训队]Crash的旅游计划

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define Maxn 200005
using namespace std;
char opt;
bool vis[Maxn];
struct edge{int next,to,dis;}e[Maxn<<1];
int N,K,size[Maxn],root=0,Min,cnt,head[Maxn],father[Maxn],deep[Maxn],f[Maxn][25],dep[Maxn];
vector<int>a[Maxn],b[Maxn];
inline void read(int &x)
{
	int f=1;x=0;char ch=getchar();
	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
inline void add(int u,int v,int w){e[++cnt].next=head[u];e[cnt].to=v;e[cnt].dis=w;head[u]=cnt;}
inline int dfs(int now,int fa)
{
	f[now][0]=fa;
	for (int i=1;i<=20;i++) f[now][i]=f[f[now][i-1]][i-1];
	for (int i=head[now];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa) continue;
		dep[v]=dep[now]+1; 
		deep[v]=deep[now]+e[i].dis;
		dfs(v,now);	
	}
}
inline int LCA(int x,int y)
{
	if (dep[x]<=dep[y]) swap(x,y);
	for (int i=20;i>=0;i--)
	{
		if (dep[f[x][i]]>=dep[y]) x=f[x][i];
		if (x==y) return x;
	}
	for (int i=20;i>=0;i--)
		if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
inline void Get_rt(int now,int fa,int Size)
{
    int Max_size=0;size[now]=1;
    for (int i=head[now];i;i=e[i].next)
    {
        int v=e[i].to;
        if (vis[v]||v==fa) continue;
        Get_rt(v,now,Size);
        Max_size=max(size[v],Max_size);
		size[now]+=size[v];
    }
    Max_size=max(Max_size,Size-size[now]);
    if (Min>Max_size) root=now,Min=Max_size;
}
inline void solve(int now,int fa)
{
	vis[now]=1;
	for (int i=head[now];i;i=e[i].next)
	{
		int v=e[i].to;
		if (v==fa||vis[v]) continue;
		Min=2e9;
		Get_rt(v,v,size[v]);
		father[root]=now;
		solve(root,now);
	}
}
inline int check(int now,int len)
{
	int ans=0;
	int l=0,r=a[now].size()-1;
	while (l<=r)
	{
		int mid=l+r>>1;
		if (a[now][mid]<=len) l=mid+1;
		else r=mid-1;
	}
	ans=l-1;
	for (int u=now;father[u];u=father[u])
	{
		int dis=deep[now]+deep[father[u]]-2*deep[LCA(now,father[u])];
		if (len-dis<0) continue;
		l=0,r=a[father[u]].size()-1;
		while (l<=r)
		{
			int mid=l+r>>1;
			if (a[father[u]][mid]<=len-dis) l=mid+1;
			else r=mid-1;
		}
		ans+=l-1;
		l=0,r=b[u].size()-1;
		while (l<=r)
		{
			int mid=l+r>>1;
			if (b[u][mid]<=len-dis) l=mid+1;
			else r=mid-1;
		}
		ans-=l-1;
	}
	return ans;
}
int main()
{
	memset(vis,0,sizeof(vis));
	cin>>opt;
	read(N),read(K);
	for (int u,v,w,i=1;i<N;i++)
	{
		read(u),read(v),read(w);
		add(u,v,w),add(v,u,w);
	}
	dfs(1,1);
	Min=2e9;
	Get_rt(1,1,N);
	solve(root,root);
	for (int i=1;i<=N;i++)
	{
		a[i].push_back(0);
		for (int j=i;father[j];j=father[j])
		{
			int len=deep[i]+deep[father[j]]-2*deep[LCA(father[j],i)];
			a[father[j]].push_back(len);
			b[j].push_back(len);
		}
	}
	for (int i=1;i<=N;i++)sort(a[i].begin(),a[i].end()),sort(b[i].begin(),b[i].end());
	for (int i=1;i<=N;i++)
	{
		int l=1,r=1e9,ans=0;
		while (l<=r)
		{
			int mid=l+r>>1;
			if (check(i,mid)>=K) ans=mid,r=mid-1;
			else l=mid+1;
		}
		cout<<ans<<endl;
	}
	return 0;
} 
/*
A 6 3
1 2 2
1 3 4
1 4 3
3 5 1
3 6 2
*/
学习小结点分树
暂无评论

发送评论 编辑评论 



























































































|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
 




颜文字
Emoji
小恐龙
花!
 


 














上一篇
下一篇