差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:线段树合并_分裂 [2020/07/06 11:27]
jxm2001 创建
+++ 2020-2021:teams:legal_string:jxm2001:线段树合并_分裂 [2021/07/14 15:53] (当前版本)
jxm2001 [算法思想]
@@ 行 1: / 行 1: @@
-====== 线段树合并 ======
+====== 线段树合并/分裂 ======
 ===== 算法简介 =====
-一种合并多个线段树(一般为权值线段树)的算法，主要用于解决染色问题，时空间复杂度 $O(n)$。
+一种快速合并、分裂线段树(一般为权值线段树)的算法，时空间复杂度 $O(m\log n)$。
 ===== 算法思想 =====
-更新线段树时动态开点，合并时如果遇到叶子节点或空结点就直接 $\text{return}$，否则跑子树。
+更新、分裂线段树时动态开点，易知更新操作时空间复杂度 $O(\log n)$。
+关于分裂操作，遇到空结点则返回。其余操作同线段树查询，遇到分裂区间的子区间则将原节点转移给新节点，然后返回。
+所以分裂操作的时空间复杂度同线段树查询操作的时间复杂度，即 $O(\log n)$。
+关于合并操作，如果遇到叶子节点或空结点就直接 $\text{return}$，否则跑子树。
+关于合并操作的时间复杂度，每次合并时间复杂度为两棵线段树的重叠部分的结点数，而每次合并一个节点等价于删除一个节点。
+每个节点至多被删除一次，所以合并操作的总时间复杂度等于空间复杂度，即 $O(m\log n)$。
 ===== 代码模板 =====
+[[https://www.luogu.com.cn/problem/P5494|洛谷p5494]]
 <hidden 查看代码>
 <code cpp>
+const int MAXN=2e5+5,MAXM=30;
+struct Node{
+	LL cnt;
+	int ch[2];
+}node[MAXN*MAXM];
+struct Pool{
+	int Stack[MAXN*MAXM],top,tot;
+	int New(){return top?Stack[top--]:++tot;}
+	void Delate(int x){
+		node[x].cnt=node[x].ch[0]=node[x].ch[1]=0;
+		Stack[++top]=x;
+	}
+}pool;
+void push_up(int k){node[k].cnt=node[node[k].ch[0]].cnt+node[node[k].ch[1]].cnt;}
+void update(int &k,int lef,int rig,int pos,int v){
+	if(!k)k=pool.New();
+	if(lef==rig)
+	return node[k].cnt+=v,void();
+	int mid=lef+rig>>1;
+	if(mid>=pos)
+	update(node[k].ch[0],lef,mid,pos,v);
+	else
+	update(node[k].ch[1],mid+1,rig,pos,v);
+	push_up(k);
+}
+void Merge(int &k1,int k2,int lef,int rig){
+	if(!k1||!k2) return k1|=k2,void();
+	if(lef==rig) return node[k1].cnt+=node[k2].cnt,pool.Delate(k2);
+	int mid=lef+rig>>1;
+	Merge(node[k1].ch[0],node[k2].ch[0],lef,mid);
+	Merge(node[k1].ch[1],node[k2].ch[1],mid+1,rig);
+	pool.Delate(k2);
+	push_up(k1);
+}
+void split(int &k1,int &k2,int lef,int rig,int L,int R){
+	if(!k1)return;
+	if(L<=lef&&rig<=R){
+		k2=k1;
+		k1=0;
+		return;
+	}
+	k2=pool.New();
+	int mid=lef+rig>>1;
+	if(mid>=L)
+	split(node[k1].ch[0],node[k2].ch[0],lef,mid,L,R);
+	if(mid<R)
+	split(node[k1].ch[1],node[k2].ch[1],mid+1,rig,L,R);
+	push_up(k1);push_up(k2);
+}
+LL Count(int k,int lef,int rig,int L,int R){
+	if(!k)return 0;
+	if(L<=lef&&rig<=R)
+	return node[k].cnt;
+	int mid=lef+rig>>1;
+	if(mid>=R)
+	return Count(node[k].ch[0],lef,mid,L,R);
+	else if(mid<L)
+	return Count(node[k].ch[1],mid+1,rig,L,R);
+	else
+	return Count(node[k].ch[0],lef,mid,L,R)+Count(node[k].ch[1],mid+1,rig,L,R);
+}
+int Rank(int k,int lef,int rig,LL rk){
+	if(node[k].cnt<rk)
+	return -1;
+	int mid=lef+rig>>1;
+	if(lef==rig)return mid;
+	if(rk<=node[node[k].ch[0]].cnt)
+	return Rank(node[k].ch[0],lef,mid,rk);
+	else
+	return Rank(node[k].ch[1],mid+1,rig,rk-node[node[k].ch[0]].cnt);
+}
+int root[MAXN],root_cnt=1;
+int main()
+{
+    int n=read_int(),m=read_int(),v,p,x,y,opt;
+    _rep(i,1,n){
+    	v=read_int();
+    	if(v)
+    	update(root[1],1,n,i,v);
+	}
+	while(m--){
+		opt=read_int(),p=read_int();
+		switch(opt){
+			case 0:
+				x=read_int(),y=read_int();
+				split(root[p],root[++root_cnt],1,n,x,y);
+				break;
+			case 1:
+				x=read_int();
+				Merge(root[p],root[x],1,n);
+				break;
+			case 2:
+				x=read_int(),y=read_int();
+				update(root[p],1,n,y,x);
+				break;
+			case 3:
+				x=read_int(),y=read_int();
+				enter(Count(root[p],1,n,x,y));
+				break;
+			case 4:
+				x=read_int();
+				enter(Rank(root[p],1,n,x));
+				break;
+		}
+	}
+    return 0;
+}
+</code>
+</hidden>
+===== 算法练习 =====
+==== 习题一 ====
+[[https://www.luogu.com.cn/problem/P4556|洛谷p4556]]
+=== 题意 ===
+给定一棵 $n$ 个节点的数，$m$ 个操作。
+每个操作三个参数 $x,y,z$，表示给结点 $x$ 到 $y$ 的树链上的每个点打上一个 $z$ 号标记。
+经过所有操作后输出每个结点被打上的最多的标记的编号(满足条件的标记存在多个时输出编号最小的)，如果该结点未被标记过，输出 $0$。
+=== 题解 1 ===
+离散化处理标记编号，防止 $\text{MLE}$。
+每个结点用一棵权值线段树维护该结点的所有标记状态，树上差分打标记，最后从叶子结点开始向上合并即可。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,MAXM=20;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt].to=v;
+	edge[edge_cnt].next=head[u];
+	head[u]=edge_cnt;
+}
+struct LCA{
+	int d[MAXN],anc[MAXN][MAXM],log2[MAXN];
+	void dfs(int u,int fa,int dep){
+		anc[u][0]=fa,d[u]=dep;
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(v==fa)
+			continue;
+			dfs(v,u,dep+1);
+		}
+	}
+	void build(int root,int n){
+		log2[1]=0;
+		_rep(i,2,n)
+		log2[i]=log2[i>>1]+1;
+		dfs(root,-1,1);
+		_rep(i,1,n){//下标从1开始
+			for(int j=1;(1<<j)<n;j++)
+			anc[i][j]=-1;
+		}
+		for(int j=1;(1<<j)<n;j++){
+			_rep(i,1,n){
+				if(anc[i][j-1]==-1)
+				continue;
+				anc[i][j]=anc[anc[i][j-1]][j-1];
+			}
+		}
+	}
+	int query(int p,int q){
+		if(d[p]<d[q])
+		swap(p,q);
+		for(int i=log2[d[p]];i>=0;i--){
+			if(d[p]-(1<<i)>=d[q])
+			p=anc[p][i];
+		}
+		if(p==q)
+		return p;
+		for(int i=log2[d[p]];i>=0;i--){
+			if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i]){
+				p=anc[p][i],q=anc[q][i];
+			}
+		}
+		return anc[p][0];
+	}
+}lca;
 const int MAXS=MAXN*60;
 int root[MAXN],tot;
 struct Node{
-	int max_cnt,ans;//自己需要维护的信息
+	int max_cnt,ans;
 	int ch[2];
 }node[MAXS];
-void push_up(int k){//自定义
+void push_up(int k){
 	if(node[node[k].ch[0]].max_cnt>=node[node[k].ch[1]].max_cnt)
 	node[k].max_cnt=node[node[k].ch[0]].max_cnt,node[k].ans=node[node[k].ch[0]].ans;
@@ 行 42: / 行 241: @@
 	Merge(node[k1].ch[1],node[k2].ch[1],mid+1,rig);
 	push_up(k1);
+}
+int X[MAXN],Y[MAXN],Z[MAXN],b[MAXN],ans[MAXN],Max_z;
+void dfs(int u){
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(lca.anc[u][0]==v)
+		continue;
+		dfs(v);
+		Merge(root[u],root[v],1,Max_z);
+	}
+	ans[u]=node[root[u]].max_cnt>0?node[root[u]].ans:0;
+}
+int main()
+{
+	int n=read_int(),q=read_int(),u,v,p;
+	_for(i,1,n){
+		u=read_int(),v=read_int();
+		Insert(u,v);
+		Insert(v,u);
+	}
+	lca.build(1,n);
+	_for(i,0,q)
+	X[i]=read_int(),Y[i]=read_int(),Z[i]=read_int();
+	memcpy(b,Z,sizeof(Z));
+	sort(b,b+q);
+	Max_z=unique(b,b+q)-b;
+	_for(i,0,q){
+		Z[i]=lower_bound(b,b+Max_z,Z[i])-b+1;
+		update(root[X[i]],1,Max_z,Z[i],1);update(root[Y[i]],1,Max_z,Z[i],1);
+		p=lca.query(X[i],Y[i]);
+		update(root[p],1,Max_z,Z[i],-1);
+		p=lca.anc[p][0];
+		if(p!=-1)
+		update(root[p],1,Max_z,Z[i],-1);
+	}
+	dfs(1);
+	_rep(i,1,n)
+	if(ans[i])
+	enter(b[ans[i]-1]);
+	else
+	enter(0);
+	return 0;
 }
 </code>
 </hidden>
-===== 算法练习 =====
+=== 题解 2 ===
-==== 习题一 ====
+考虑树剖，将树上问题转换为区间问题，更新路径时只打差分打标记。
-[[https://www.luogu.com.cn/problem/P4556|洛谷p4556]]
+最后询问时只建一棵权值线段树，依次释放区间上每个位置的标记，维护标记前缀和、答案。
+时间复杂度 $O(m\log^2 n)$，空间复杂度 $O(m\log n)$，但常数远小于线段树合并。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,MAXM=20;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt].to=v;
+	edge[edge_cnt].next=head[u];
+	head[u]=edge_cnt;
+}
+struct lazy_tag{
+	int v,next;
+}lazy[MAXN*MAXM];
+int head_2[MAXN],lazy_cnt;
+void Insert_2(int u,int v){
+	lazy[++lazy_cnt].v=v;
+	lazy[lazy_cnt].next=head_2[u];
+	head_2[u]=lazy_cnt;
+}
+int Max_cnt[MAXN<<2],Ans[MAXN<<2],lef[MAXN<<2],rig[MAXN<<2];
+void build(int k,int L,int R){
+	lef[k]=L,rig[k]=R;
+	int M=L+R>>1;
+	if(L==R)return Ans[k]=M,void();
+	build(k<<1,L,M);
+	build(k<<1|1,M+1,R);
+}
+void push_up(int k){
+	if(Max_cnt[k<<1]>=Max_cnt[k<<1|1]){
+		Max_cnt[k]=Max_cnt[k<<1];
+		Ans[k]=Ans[k<<1];
+	}
+	else{
+		Max_cnt[k]=Max_cnt[k<<1|1];
+		Ans[k]=Ans[k<<1|1];
+	}
+}
+void update(int k,int pos,int v){
+	if(lef[k]==rig[k])
+	return Max_cnt[k]+=v,void();
+	int mid=lef[k]+rig[k]>>1;
+	if(pos<=mid)
+	update(k<<1,pos,v);
+	else
+	update(k<<1|1,pos,v);
+	push_up(k);
+}
+int d[MAXN],sz[MAXN],f[MAXN],dfs_id[MAXN],inv_id[MAXN],dfs_t;
+int h_son[MAXN],mson[MAXN],p[MAXN];
+void dfs_1(int u,int fa,int depth){
+	sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)
+		continue;
+		dfs_1(v,u,depth+1);
+		sz[u]+=sz[v];
+		if(sz[v]>mson[u]){
+			h_son[u]=v;
+			mson[u]=sz[v];
+		}
+	}
+}
+void dfs_2(int u,int top){
+	dfs_id[u]=++dfs_t;inv_id[dfs_t]=u;p[u]=top;
+	if(mson[u])
+	dfs_2(h_son[u],top);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==f[u]||v==h_son[u])
+		continue;
+		dfs_2(v,v);
+	}
+}
+void update_path(int u,int v,int w){
+	while(p[u]!=p[v]){
+		if(d[p[u]]<d[p[v]])
+		swap(u,v);
+		Insert_2(dfs_id[p[u]],w);
+		Insert_2(dfs_id[u]+1,-w);
+		u=f[p[u]];
+	}
+	if(d[u]>d[v])
+	swap(u,v);
+	Insert_2(dfs_id[u],w);
+	Insert_2(dfs_id[v]+1,-w);
+}
+void update_node(int u){
+	for(int i=head_2[u];i;i=lazy[i].next){
+		if(lazy[i].v>0)
+		update(1,lazy[i].v,1);
+		else
+		update(1,-lazy[i].v,-1);
+	}
+}
+int X[MAXN],Y[MAXN],Z[MAXN],b[MAXN],ans[MAXN];
+int main()
+{
+	int n=read_int(),q=read_int(),u,v,w;
+	_for(i,1,n){
+		u=read_int(),v=read_int();
+		Insert(u,v);
+		Insert(v,u);
+	}
+	_for(i,0,q)
+	X[i]=read_int(),Y[i]=read_int(),Z[i]=read_int();
+	memcpy(b,Z,sizeof(Z));
+	sort(b,b+q);
+	int Max_z=unique(b,b+q)-b;
+	dfs_1(1,-1,0);
+	dfs_2(1,1);
+	build(1,1,Max_z);
+	_for(i,0,q)
+	update_path(X[i],Y[i],lower_bound(b,b+Max_z,Z[i])-b+1);
+	_rep(i,1,n){
+		update_node(i);
+		ans[inv_id[i]]=Max_cnt[1]>0?b[Ans[1]-1]:0;
+	}
+	_rep(i,1,n)
+	enter(ans[i]);
+	return 0;
+}
+</code>
+</hidden>
+==== 习题二 ====
+[[https://www.luogu.com.cn/problem/P3224|洛谷p3224]]
 === 题意 ===
-给定一棵 $n$ 个节点的数，$m$ 个操作。
+给定 $n$ 个点，所有点的点权恰好为 $1 \sim n$ 的排列，接下来两种操作。
-每个操作三个参数 $x,y,z$，表示给结点 $x$ 到 $y$ 的树链上的每个点打上一个 $z$ 号标记。
+  - 询问与某点 $x$ 联通的点集中的第 $k$ 大元素的编号，若不存在输出 $-1$。
+  - 连接点 $u$、$v$。
-经过所有操作后输出每个结点被打上的最多的标记的编号(满足条件的标记存在多个时输出编号最小的)，如果该结点未被标记过，输出 $0$。
+=== 题解 ===
-=== 题解 1 ===
+每个点维护一棵权值线段树，并查集维护连通分量。
+对操作 $1$ 类似名次树操作，对操作 $2$ 使用线段树合并即可，时空间复杂度 $O(n\log n)$。
 <hidden 查看代码>
 <code cpp>
+const int MAXN=1e5+5,MAXS=MAXN*40;
+int root[MAXN],tot;
+struct Node{
+	int sz;
+	int ch[2];
+}node[MAXS];
+void push_up(int k){node[k].sz=node[node[k].ch[0]].sz+node[node[k].ch[1]].sz;}
+void update(int &k,int lef,int rig,int pos){
+	k=++tot;
+	node[k].sz++;
+	if(lef==rig) return;
+	int mid=lef+rig>>1;
+	if(pos>mid)
+	update(node[k].ch[1],mid+1,rig,pos);
+	else
+	update(node[k].ch[0],lef,mid,pos);
+}
+void Merge(int &k1,int k2,int lef,int rig){
+	if(!k1||!k2) return k1|=k2,void();
+	int mid=lef+rig>>1;
+	Merge(node[k1].ch[0],node[k2].ch[0],lef,mid);
+	Merge(node[k1].ch[1],node[k2].ch[1],mid+1,rig);
+	push_up(k1);
+}
+int query(int k,int lef,int rig,int rk){
+	if(rk>node[k].sz)return 0;
+	int mid=lef+rig>>1;
+	if(lef==rig)return mid;
+	if(rk<=node[node[k].ch[0]].sz)
+	return query(node[k].ch[0],lef,mid,rk);
+	else
+	return query(node[k].ch[1],mid+1,rig,rk-node[node[k].ch[0]].sz);
+}
+int kth[MAXN],Rank[MAXN],p[MAXN],n;
+int Find(int x){return x==p[x]?x:p[x]=Find(p[x]);}
+void Merge(int u,int v){
+	int x=Find(u),y=Find(v);
+	if(x!=y){
+		p[y]=x;
+		Merge(root[x],root[y],1,n);
+	}
+}
+int main()
+{
+	n=read_int();
+	int m=read_int(),u,v;
+	Rank[0]=-1;
+	_rep(i,1,n){
+		kth[i]=read_int(),p[i]=i,Rank[kth[i]]=i;
+		update(root[i],1,n,kth[i]);
+	}
+	while(m--){
+		u=read_int(),v=read_int();
+		Merge(u,v);
+	}
+	int q=read_int();
+	char opt;
+	while(q--){
+		opt=get_char(),u=read_int(),v=read_int();
+		if(opt=='Q')
+		enter(Rank[query(root[Find(u)],1,n,v)]);
+		else
+		Merge(u,v);
+	}
+	return 0;
+}
+</code>
+</hidden>
+==== 习题三 ====
+[[https://www.luogu.com.cn/problem/P1600|洛谷p1600]]
+=== 题意 ===
+一棵 $n$ 个结点的树，树上有 $m$ 个玩家，第 $i$ 个玩家的起点为 $s_i$，终点为 $t_i$，每个玩家每秒移动一条边。
+在每个结点放置一名观察者，第 $i$ 个结点的观察者会在第 $w_i$ 秒观察到达该点的玩家。
+玩家到终点后立即消失，但可以在该时刻被观察者观测。
+问每个观察者观察到的玩家数量。
+=== 题解 1 ===
+先将树转化为一棵有根树，考虑玩家对的结点 $u$ 的观察者的贡献。
+可以把玩家的运动分解为 $s\to \text{LCA}(s,t)\to t$。
+考虑 $s\to \text{LCA}(s,t)$，只当且仅当 $u\in \{s\to \text{LCA}(s,t)\}$ 且 $w_u=d_s-d_u$ 才产生贡献。
+考虑 $\text{LCA}(s,t)\to t$，只当且仅当 $u\in \{\text{LCA}(s,t)\to t\}$ 且 $\text{dist}(s,t)-w_u=d_t-d_u$ 才产生贡献。
+分离变量，得 $w_u+d_u=d_s$ 和 $w_u-d_u=\text{dist}(s,t)-d_t$，可以考虑每个结点用两个桶维护可以产生贡献的 $d_s$ 和 $\text{dist}(s,t)-d_t$ 的数量。
+然后考虑怎么处理 $u\in \{s\to \text{LCA}(s,t)\}$ 和 $u\in \{\text{LCA}(s,t)\to t\}$ 这两个限制条件。
+考虑树上差分，在 $s$ 和 $t$ 结点打上增加标记， $\text{LCA}(s,t)$ 结点打上删除标记。
+对每个结点，先 $\text{dfs}$ 子节点，然后处理增加标记，然后查询答案，最后处理删除标记。
+考虑如果 $\text{LCA}(s,t)$ 满足  $w_{\text{LCA}(s,t)}+d_{\text{LCA}(s,t)}=d_s$，必有 $w_{\text{LCA}(s,t)}-d_{\text{LCA}(s,t)}=\text{dist}(s,t)-d_t$，导致 $s$ 和 $t$ 重复贡献，所以要提前处理。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=3e5+5;
+int head[MAXN],edge_cnt;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+void Insert(int u,int v){
+	edge[++edge_cnt].next=head[u];
+	edge[edge_cnt].to=v;
+	head[u]=edge_cnt;
+}
+struct LCA{
+	int d[MAXN],sz[MAXN],f[MAXN];
+	int h_son[MAXN],mson[MAXN],p[MAXN];
+	void dfs_1(int u,int fa,int depth){
+		sz[u]=1;f[u]=fa;d[u]=depth;mson[u]=0;
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(v==fa)
+			continue;
+			dfs_1(v,u,depth+1);
+			sz[u]+=sz[v];
+			if(sz[v]>mson[u])
+			h_son[u]=v,mson[u]=sz[v];
+		}
+	}
+	void dfs_2(int u,int top){
+		p[u]=top;
+		if(mson[u])dfs_2(h_son[u],top);
+		for(int i=head[u];i;i=edge[i].next){
+			int v=edge[i].to;
+			if(v==f[u]||v==h_son[u])
+			continue;
+			dfs_2(v,v);
+		}
+	}
+	void Init(int root){dfs_1(root,-1,0);dfs_2(root,root);}
+	int query_lca(int u,int v){
+		while(p[u]!=p[v]){
+			if(d[p[u]]<d[p[v]])swap(u,v);
+			u=f[p[u]];
+		}
+		return d[u]<d[v]?u:v;
+	}
+	int query_dis(int u,int v){return d[u]+d[v]-2*d[query_lca(u,v)];}
+}lca;
+int C[MAXN<<2],*c1=C,*c2=C+MAXN*3;
+struct Path{
+	int u,v,len;
+}path[MAXN];
+struct Tag{
+	int p,next;
+}tag[MAXN<<1];
+int w[MAXN],head_s[MAXN],head_t[MAXN],head_lca[MAXN],tot,ans[MAXN];
+void Insert_t(int node,int k){
+	tag[++tot].next=head_t[node];
+	tag[tot].p=k;
+	head_t[node]=tot;
+}
+void Insert_lca(int node,int k){
+	tag[++tot].next=head_lca[node];
+	tag[tot].p=k;
+	head_lca[node]=tot;
+}
+void dfs(int u,int fa){
+	int t1=c1[w[u]+lca.d[u]],t2=c2[w[u]-lca.d[u]];
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)
+		continue;
+		dfs(v,u);
+	}
+	c1[lca.d[u]]+=head_s[u];
+	for(int i=head_t[u];i;i=tag[i].next){
+		Path& p=path[tag[i].p];
+		c2[p.len-lca.d[p.v]]++;
+	}
+	ans[u]+=c1[w[u]+lca.d[u]]-t1+c2[w[u]-lca.d[u]]-t2;
+	for(int i=head_lca[u];i;i=tag[i].next){
+		Path& p=path[tag[i].p];
+		c1[lca.d[p.u]]--;
+		c2[p.len-lca.d[p.v]]--;
+	}
+}
+int main()
+{
+    int n=read_int(),m=read_int(),u,v;
+    _for(i,1,n){
+    	u=read_int(),v=read_int();
+    	Insert(u,v);
+    	Insert(v,u);
+	}
+	lca.Init(1);
+	_rep(i,1,n)
+	w[i]=read_int();
+	_rep(i,1,m){
+		path[i].u=u=read_int(),path[i].v=v=read_int();
+		int p=lca.query_lca(u,v);
+		path[i].len=lca.d[u]+lca.d[v]-lca.d[p]*2;
+		head_s[u]++;
+		Insert_t(v,i);
+		Insert_lca(p,i);
+		if(lca.d[p]+w[p]==lca.d[u])
+		ans[p]--;
+	}
+	dfs(1,0);
+	_rep(i,1,n)
+	space(ans[i]);
+    return 0;
+}
 </code>
 </hidden>
@@ 行 71: / 行 660: @@
 === 题解 2 ===
+树上差分的思路同题解 1，但这次考虑用线段树代替桶维护答案，对每个点可以直接处理贡献，然后从叶子结点向上合并线段树即可。
+贴了一段别人的代码。
 <hidden 查看代码>
 <code cpp>
+#include <bits/stdc++.h>
+using namespace std;
+char ch;
+bool fi;
+template<typename _Type>
+inline void read(_Type&d) {
+	d=0, fi=0, ch=getchar();
+	while(!isdigit(ch) && ch!='-') ch=getchar();
+	if(ch=='-') fi=1, ch=getchar();
+	do d=d*10+ch-'0', ch=getchar();
+	while(isdigit(ch));
+	if(fi) d=~d+1;
+}
+const int N=300000+1;
+struct DymSegTree {
+	int ls[30*N],rs[30*N],sum[30*N],rt[N];
+	int rb[30*N],top,tot;
+	inline int newNode() {
+		return top?rb[top--]:++tot;
+	}
+	inline void delNode(int x) {
+		rb[++top]=x;
+		ls[x]=rs[x]=sum[x]=0;
+	}
+	void modify(int&x,int l,int r,int pos,int val) {
+		if(!x) x=newNode();
+		if(l==r) { sum[x]+=val; return;}
+		int mid=(l+r)>>1;
+		if(pos<=mid) modify(ls[x],l,mid,pos,val);
+		else modify(rs[x],mid+1,r,pos,val);
+		sum[x]=sum[ls[x]]+sum[rs[x]];
+	}
+	int merge(int x,int y,int l,int r) {
+		if(!x||!y) return x|y;
+		int now=newNode();
+		if(l==r) sum[now]=sum[x]+sum[y];
+		else {
+			int mid=(l+r)>>1;
+			ls[now]=merge(ls[x],ls[y],l,mid);
+			rs[now]=merge(rs[x],rs[y],mid+1,r);
+			sum[now]=sum[ls[now]]+sum[rs[now]];
+		}
+		delNode(x), delNode(y);
+		return now;
+	}
+	int query(int x,int l,int r,int pos) {
+		if(l==r) return sum[x];
+		int mid=(l+r)>>1;
+		return (mid>=pos) ? query(ls[x],l,mid,pos)
+			:query(rs[x],mid+1,r,pos);
+	}
+} T1, T2;
+vector<int> E[N];
+vector<int> G[N];
+struct Player {
+	int u,v,tim;
+} a[N];
+int n,m,w[N],ans[N],dep[N],fa[N][22];
+void pre(int x,int pa) {
+	dep[x]=dep[fa[x][0]=pa]+1;
+	for(int i=1; (1<<i)<=dep[x]; ++i)
+		fa[x][i]=fa[fa[x][i-1]][i-1];
+	for(int y:E[x]) if(y!=pa) pre(y,x);
+}
+inline int lca(int x,int y) {
+	if(dep[x]<dep[y]) x^=y^=x^=y;
+	int dif=dep[x]-dep[y];
+	for(int i=20; ~i; --i)
+		if(dif&(1<<i)) x=fa[x][i];
+	if(x==y) return x;
+	for(int i=20; ~i; --i) if(fa[x][i]!=fa[y][i])
+		x=fa[x][i], y=fa[y][i];
+	return fa[x][0];
+}
+void dfs(int x,int pa) {
+	for(int y:E[x]) if(y!=pa) dfs(y,x);
+	for(int i:G[x]) T2.modify(T2.rt[x],1,N+N, a[i].tim-dep[a[i].v]+N,-1);
+	ans[x]=T1.query(T1.rt[x],1,N+N, dep[x]+w[x])
+		  +T2.query(T2.rt[x],1,N+N, w[x]-dep[x]+N);
+	for(int i:G[x]) T1.modify(T1.rt[x],1,N+N, dep[a[i].u],-1);
+	if(pa) {
+		T1.rt[pa]=T1.merge(T1.rt[pa],T1.rt[x],1,N+N);
+		T2.rt[pa]=T2.merge(T2.rt[pa],T2.rt[x],1,N+N);
+	}
+}
+int main() {
+	read(n); read(m);
+	for(int x,y,i=n; --i; ) {
+		read(x); read(y);
+		E[x].push_back(y);
+		E[y].push_back(x);
+	}
+	pre(1,0);
+	for(int i=1; i<=n; ++i) read(w[i]);
+	for(int i=1; i<=m; ++i) {
+		read(a[i].u); read(a[i].v);
+		int LCA=lca(a[i].u,a[i].v);
+		a[i].tim=dep[a[i].u]+dep[a[i].v]-2*dep[LCA];
+		T1.modify(T1.rt[a[i].u],1,N+N, dep[a[i].u],1);
+		T2.modify(T2.rt[a[i].v],1,N+N, a[i].tim-dep[a[i].v]+N,1);
+		G[LCA].push_back(i);
+	}
+	dfs(1,0);
+	for(int i=1; i<=n; ++i) printf("%d ",ans[i]);
+	return 0;
+}
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具