差别

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

--- 2020-2021:teams:legal_string:jxm2001:线段树合并_分裂 [2020/07/06 20:25]
jxm2001
+++ 2020-2021:teams:legal_string:jxm2001:线段树合并_分裂 [2021/07/14 15:53] (当前版本)
jxm2001 [算法思想]
@@ 行 1: / 行 1: @@
-====== 线段树合并 ======
+====== 线段树合并/分裂 ======
 ===== 算法简介 =====
-一种合并多个线段树(一般为权值线段树)的算法，主要用于解决染色问题，时空间复杂度 $O(m\log n)$。
+一种快速合并、分裂线段树(一般为权值线段树)的算法，时空间复杂度 $O(m\log n)$。
 ===== 算法思想 =====
-更新线段树时动态开点，合并时如果遇到叶子节点或空结点就直接 $\text{return}$，否则跑子树。
+更新、分裂线段树时动态开点，易知更新操作时空间复杂度 $O(\log n)$。
-关于空间复杂度，每次动态开点 $O(\log n)$，所以总空间复杂度 $O(m\log n)$，注意线段树是四倍空间。
+关于分裂操作，遇到空结点则返回。其余操作同线段树查询，遇到分裂区间的子区间则将原节点转移给新节点，然后返回。
-关于时间复杂度，每次合并时间复杂度为两棵线段树的重叠部分的结点数，所以不会超过较小的那棵线段树的结点数。
+所以分裂操作的时空间复杂度同线段树查询操作的时间复杂度，即 $O(\log n)$。
-所以合并操作的总时间复杂度等于动态开点总数，即 $O(m\log n)$。
+关于合并操作，如果遇到叶子节点或空结点就直接 $\text{return}$，否则跑子树。
+关于合并操作的时间复杂度，每次合并时间复杂度为两棵线段树的重叠部分的结点数，而每次合并一个节点等价于删除一个节点。
+每个节点至多被删除一次，所以合并操作的总时间复杂度等于空间复杂度，即 $O(m\log n)$。
 ===== 代码模板 =====
+[[https://www.luogu.com.cn/problem/P5494|洛谷p5494]]
 <hidden 查看代码>
 <code cpp>
-const int MAXS=MAXN*60;
+const int MAXN=2e5+5,MAXM=30;
-int root[MAXN],tot;
 struct Node{
-	int max_cnt,ans;//自己需要维护的信息
+	LL cnt;
 	int ch[2];
-}node[MAXS];
+}node[MAXN*MAXM];
-void push_up(int k){//自定义
+struct Pool{
-	if(node[node[k].ch[0]].max_cnt>=node[node[k].ch[1]].max_cnt)
+	int Stack[MAXN*MAXM],top,tot;
-	node[k].max_cnt=node[node[k].ch[0]].max_cnt,node[k].ans=node[node[k].ch[0]].ans;
+	int New(){return top?Stack[top--]:++tot;}
-	else
+	void Delate(int x){
-	node[k].max_cnt=node[node[k].ch[1]].max_cnt,node[k].ans=node[node[k].ch[1]].ans;
+		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=++tot;
+	if(!k)k=pool.New();
-	if(lef==rig) return node[k].max_cnt+=v,node[k].ans=pos,void();
+	if(lef==rig)
+	return node[k].cnt+=v,void();
 	int mid=lef+rig>>1;
-	if(pos>mid)
+	if(mid>=pos)
-	update(node[k].ch[1],mid+1,rig,pos,v);
-	else
 	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].max_cnt+=node[k2].max_cnt,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>
@@ 行 74: / 行 157: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e5+5,MAXM=20;
 struct Edge{
@@ 行 261: / 行 297: @@
 <hidden 查看代码>
 <code cpp>
-#include <iostream>
-#include <cstdio>
-#include <cstdlib>
-#include <algorithm>
-#include <string>
-#include <sstream>
-#include <cstring>
-#include <cctype>
-#include <cmath>
-#include <vector>
-#include <set>
-#include <map>
-#include <stack>
-#include <queue>
-#include <ctime>
-#include <cassert>
-#define _for(i,a,b) for(int i=(a);i<(b);++i)
-#define _rep(i,a,b) for(int i=(a);i<=(b);++i)
-#define mem(a,b) memset(a,b,sizeof(a))
-using namespace std;
-typedef long long LL;
-inline int read_int(){
-	int t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline LL read_LL(){
-	LL t=0;bool sign=false;char c=getchar();
-	while(!isdigit(c)){sign|=c=='-';c=getchar();}
-	while(isdigit(c)){t=(t<<1)+(t<<3)+(c&15);c=getchar();}
-	return sign?-t:t;
-}
-inline char get_char(){
-	char c=getchar();
-	while(c==' '||c=='\n'||c=='\r')c=getchar();
-	return c;
-}
-inline void write(LL x){
-	register char c[21],len=0;
-	if(!x)return putchar('0'),void();
-	if(x<0)x=-x,putchar('-');
-	while(x)c[++len]=x%10,x/=10;
-	while(len)putchar(c[len--]+48);
-}
-inline void space(LL x){write(x),putchar(' ');}
-inline void enter(LL x){write(x),putchar('\n');}
 const int MAXN=1e5+5,MAXM=20;
 struct Edge{
@@ 行 433: / 行 422: @@
 </hidden>
+==== 习题二 ====
+[[https://www.luogu.com.cn/problem/P3224|洛谷p3224]]
+=== 题意 ===
+给定 $n$ 个点，所有点的点权恰好为 $1 \sim n$ 的排列，接下来两种操作。
+  - 询问与某点 $x$ 联通的点集中的第 $k$ 大元素的编号，若不存在输出 $-1$。
+  - 连接点 $u$、$v$。
+=== 题解 ===
+每个点维护一棵权值线段树，并查集维护连通分量。
+对操作 $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>
+=== 题解 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

用户工具

站点工具

差别

页面工具