Qinshihuang's Blog

tmc的小窝

0%

点分治

发表于

点分治善于处理大规模的树上问题。

一个使用点分治的特征是：要求的问题与谁是树的根没有太大关系。

点分治思想

点分治 1：

给定一棵树，边有边权，判定树上长度等于 $k$ 的路径是否存在。多次询问，$n\le10^4,m\le100$。

首先考虑暴力，就是枚举 $n$ 对点利用树上差分进行求解，时间复杂度是 $O(mn^2\log n)$，肯定过不去。

我们发现钦定 $1$ 为根的时候，对于 $u$ 的子树，子树内的路径只有两种：穿过 $u$ 的和不穿过 $u$ 的。我们能不能快速统计出穿过 $u$ 的路径长度，再递归到子树中去处理不穿过 $u$ 的路径呢？

答案是肯定的，因为我们有一个快速的方法来查找穿过 $u$ 的路径长度数量：由于跨过 $u$ 的路径两端点最近公共祖先一定为 $u$，因此我们枚举 $u$ 的儿子 $v$，并且维护一个数组 $b$，存储在 $v$ 之前遍历到的儿子对应子树内所有点的深度，其中有 $b_i$ 个点深度为 $i$。此时我们遍历 $v$ 对应的子树，求出新的深度数组并且动态维护和为 $k$ 的路径对数。这样时间复杂度显然是 $O(\mathrm{siz}_u)$ 的，因为子树中每个点恰好遍历一次。

接下来我们只需要再选择儿子进行递归求解问题就可以了。时间复杂度？诶，怎么是 $O(mn\cdot dep)$ 的？？？

这时间复杂度肯定不对啊，一条链就卡死了。关键在于我们选取的分治点不对，实际上有更好的方法。

本质上，我们发现在递归到 $v$ 子树内查询的时候，选择谁并不重要，因此我们可以不选择 $v$ 而换一个点，比如 $v$ 子树内的重心。

可以证明，每次分治选择子树重心的时候，总时间复杂度是 $O(n\log n)$ 的。

证明 重心的性质之一是以重心为根的时候子树大小的最大值不会超过 $\dfrac n2$，因此每次分治之后最大的子树大小都会减半，因此只会有 $O(\log n)$ 层递归，而每层递归都会遍历所有的点，是 $O(n)$ 的，因此总时间复杂度是 $O(n\log n)$。

当然这货常数非常大。

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
89
90
91
92
93
94
95
96
97
98
99
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
#define il inline
#define N 10005
il ll read() {
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') {f=-1;} c=getchar();}
	while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
struct Edge {
	ll nxt,u,v,w;
	Edge() {}
	Edge(ll _nxt,ll _u,ll _v,ll _w) {nxt=_nxt,u=_u,v=_v,w=_w;}
};
Edge edge[N<<1];
int head[N],num_edge;
il void add_edge(int u,int v,int w) {
	edge[++num_edge]=Edge(head[u],u,v,w);
	head[u]=num_edge;
}
ll n,m,k[105],root,res,siz[N],totsize,que[N],tot,dis[N];
bool bin[10000005];
bool vis[N],haveans[105];
il void getroot(int u,int fa) {
	siz[u]=1;
	ll maxn=0;
	for(int i=head[u];i;i=edge[i].nxt) {
		int v=edge[i].v;
		if(v==fa||vis[v]) continue;
		getroot(v,u);
		siz[u]+=siz[v];
		maxn=max(maxn,siz[v]);
	}
	maxn=max(maxn,totsize-siz[u]);
	if(maxn<res) res=maxn,root=u;
}
il void dfs_dis(int u,int fa) {
	if(dis[u]>10000000) return;
	que[++tot]=dis[u];
	for(int i=head[u];i;i=edge[i].nxt) {
		int v=edge[i].v,w=edge[i].w;
		if(v==fa||vis[v]) continue;
		dis[v]=dis[u]+w;
		dfs_dis(v,u);
	}
}
il void solve(int u) {
	vis[u]=1;
	bin[0]=1;
	vector<int> a;
	for(int i=head[u];i;i=edge[i].nxt) {
		int v=edge[i].v,w=edge[i].w;
		if(vis[v]) continue;
		tot=0,dis[v]=w;
		dfs_dis(v,0);
		for(int j=1;j<=tot;j++) for(int kk=1;kk<=m;kk++) {
			if(k[kk]>=que[j]&&bin[k[kk]-que[j]]) haveans[kk]=1;
		}
		for(int j=1;j<=tot;j++) {
			bin[que[j]]=1;
			a.push_back(que[j]);
		}
	}
	for(int i=0;i<a.size();i++) bin[a[i]]=0;
	for(int i=head[u];i;i=edge[i].nxt) {
		int v=edge[i].v,w=edge[i].w;
		if(vis[v]) continue;
		res=totsize=siz[v];
		getroot(v,0);
		solve(root);
	}
}
il void clean() {
	for(int i=1;i<=n;i++) siz[i]=vis[i]=dis[i]=0;
}
int main() {
	n=read(),m=read();
	for(int i=1;i<n;i++) {
		ll u=read(),v=read(),w=read();
		add_edge(u,v,w);
		add_edge(v,u,w);
	}
	for(int i=1;i<=m;i++) k[i]=read();
	res=totsize=n;
	getroot(1,0);
	solve(root);
	for(int i=1;i<=m;i++) {
		if(haveans[i]) printf("AYE\n");
		else printf("NAY\n");
	}
	return 0;
}

点分树

震波：

给定一棵树，点有点权 $a_u$，支持以下两种操作：

  • 给定一个点 $u$ 和一个定值 $k$，求出
  • 修改一个点 $u$ 的点权为 $x$。

$n,q\le10^5$，强制在线。

假设我们有 $100^{100^{100}}\mathrm{GB}$ 的空间限制怎么做。进行点分治，对每个点维护距离它为 $i$ 的点点权和，就可以了，但是空间复杂度肯定炸飞。

问题的关键在于树的深度可能是 $O(n)$ 的。但是在我们眼皮底下就有一个深度为 $O(\log n)$ 的东西：点分治的深度。

我们把原树 $\mathcal T$ 点分治过程中遍历到的点按照遍历的次序先后建成一棵新的有根重构树 $\mathcal T^\prime$，显然这棵树的深度是 $O(\log n)$ 的，但是它和原树在结构上几乎没有关系，除了一点：对于点 $u,v$，记 $\mathrm{lca}$ 为 $u,v$ 在 $\mathcal T^\prime$ 上的最近公共祖先，那么 $\mathrm{lca}$ 一定在原树 $\mathcal T$ 的 $(u,v)$ 路径上。

虽然这是显然的，但这就足够了。

对于一次询问，我们从枚举 $y$ 改为枚举 $x,y$ 在 $\mathcal T^\prime$ 上的 LCA $z$ 点。由于 $z$ 一定是 $x$ 的祖先所以只会枚举 $O(\log n)$ 次，复杂度是对的。那么我们要求的答案就是

这里 $\operatorname{dis}(u,v)$ 是 $u,v$ 在 $\mathcal T$ 上的距离。

首先考虑怎样的 $y$ 满足 $\operatorname{LCA}(x,y)=z$，显然就是 $\mathcal T^\prime$ 中 $z$ 子树中的点扣掉 $x$ 子树中的点组成的集合。考虑使用容斥来扣除 $x$ 子树内的贡献。我们对于一个点 $x$，维护两棵动态开点线段树，其中下标为深度：

  • 第一棵线段树的 $t_i$ 表示在 $\mathcal T^\prime$ 的 $x$ 子树中，所有满足 $\operatorname{dis}(x,u)=i$ 的 $u$ 数量。
  • 第二棵线段树的 $t_i^\prime$ 表示在 $\mathcal T^\prime$ 的 $\mathrm{fa}_x$ 的子树中，所有满足 $\operatorname{dis}(\mathrm{fa}_x,u)$ 的 $u$ 数量。

为什么不能直接不维护第二棵树，而扣除第一棵树中的贡献？原因和点分树的结构有关，因为点分树中父亲和儿子的关系已经被完全打乱，因此我们不能直接用距离的和来表示合并后路径的长度。所以我们必须这样维护才能正确的容斥。

这样子就做完了，修改的时候直接暴力跳父亲修改即可。

总结：点分树的核心性质是树高 $O(\log n)$，这个性质使得很多时间复杂度为 $O(dep)$ 的在一般树上不正经的暴力算法都有正确的复杂度，并以此来解决问题。

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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
#define il inline
#define N 100005
#define lc(x) (tr[x].lc)
#define rc(x) (tr[x].rc)
il ll read() {
	ll x=0,f=1;char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') {f=-1;} c=getchar();}
	while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
struct sgt {
	int lc,rc;
	int val;
	sgt() {lc=rc=val=0;}
};
sgt tr[N*100];
int root[N][2];
int n,q,a[N],siz[N],rt,res,totsize,f[N][17],dep[N],ff[N],tot;
bool vis[N];
vector<int> g[N],gg[N];
void dfs_fa(int u,int fa) {
	f[u][0]=fa;
	for(int i=1;i<=16;i++) f[u][i]=f[f[u][i-1]][i-1];
	for(auto v:g[u]) {
		if(v==fa) continue;
		dep[v]=dep[u]+1;
		dfs_fa(v,u);
	}
}
int LCA(int x,int y) {
	if(dep[x]<dep[y]) swap(x,y);
	for(int i=16;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i];
	if(x==y) return x;
	for(int i=16;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
	return f[x][0];
}
il int dist(int x,int y) {return dep[x]+dep[y]-2*dep[LCA(x,y)];}
void getroot(int u,int fa) {
	siz[u]=1;
	int maxn=0;
	for(auto v:g[u]) {
		if(v==fa||vis[v]) continue;
		getroot(v,u);
		siz[u]+=siz[v];
		maxn=max(maxn,siz[v]);
	}
	maxn=max(maxn,totsize-siz[u]);
	if(maxn<res) res=maxn,rt=u;
}
void solve(int u) {
	vis[u]=1;
	for(auto v:g[u]) {
		if(vis[v]) continue;
		res=totsize=siz[u];
		getroot(v,0);
		gg[u].push_back(rt);
		gg[rt].push_back(u);
		ff[rt]=u;
		solve(rt);
	}
}
il void push_up(int now) {
	tr[now].val=tr[lc(now)].val+tr[rc(now)].val;
}
void modify(int p,int l,int r,int &now,int k) {
	if(!now) now=++tot;
	if(l==r) {
		tr[now].val+=k;
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid) modify(p,l,mid,lc(now),k);
	else modify(p,mid+1,r,rc(now),k);
	push_up(now);
}
int query(int qx,int qy,int l,int r,int now) {
	if(!now) return 0;
	if(qx<=l&&r<=qy) return tr[now].val;
	int mid=(l+r)>>1,ans=0;
	if(qx<=mid) ans+=query(qx,qy,l,mid,lc(now));
	if(mid<qy) ans+=query(qx,qy,mid+1,r,rc(now));
	return ans;
}
il void update(int u,int k) {
	int cur=u;
	while(cur) {
		modify(dist(cur,u),0,n-1,root[cur][0],k);
		if(ff[cur]) modify(dist(ff[cur],u),0,n-1,root[cur][1],k);
		cur=ff[cur];
	}
}
il int ask(int u,int k) {
	int cur=u,fat=0,ans=0;
	while(cur) {
		if(dist(cur,u)>k) {
			fat=cur,cur=ff[cur];
			continue;
		}
		ans+=query(0,k-dist(cur,u),0,n-1,root[cur][0]);
		if(fat!=0) ans-=query(0,k-dist(cur,u),0,n-1,root[fat][1]);
		fat=cur;cur=ff[cur];
	}
	return ans;
}
int main() {
	n=read(),q=read();
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<n;i++) {
		int u=read(),v=read();
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs_fa(1,0);
	res=totsize=n;
	getroot(1,0);
	solve(rt);
	for(int i=1;i<=n;i++) update(i,a[i]);
	int lans=0;
	while(q--) {
		int opt=read(),x=read()^lans,y=read()^lans;
		if(opt==0) printf("%d\n",lans=ask(x,y));
		else {
			update(x,y-a[x]);
			a[x]=y;
		}
	}
	return 0;
}