2 条题解

  • 0
    @ 2025-10-8 16:52:36

    lzy的题解： /* 思路： 我们要把点的颜色转换成连向父节点的边的颜色，这样每次换颜色就只用处理与一条边的关系，不这样做我们就会被菊花图卡。 所以我们就必须维护有根树（根不能换），不能用makeroot来改变树的形状。 我们定义两棵树，一棵为为黑，一棵为白，每个点会同时在两棵树出现。 因为对于一个有色联通块(树)，只有根的父亲的颜色与其他点的父亲的颜色不同。 (联通块的根为1时需要特判) 所以我们每次换颜色只处理一条边的在两棵树上的断（连）就行了。 (一个联通块就是边越来越多，最后汇合而成的)（理由有点牵强，但本题本来就不好讲） 重点在于查询——LCT所维护的森林的每棵树的节点的深度要保证严格递增，但是在树上的联通块的节点可能深度一样。那怎么办呢？ 我们在splay节点(trnode)多定义一个变量u，表示其他子树节点的总数——因为父亲只认得两个孩子（悲催的家庭）,这样我们就能保证正确性了。 全局(原树)的根设为1。 查询时，我们把x(询问的元素)access并splay上去,再一直往左儿子跳，找到根(不是全局的)。因为根的颜色可能与x同，也可能不同。（只有根为1时,根的颜色才有可能与x的颜色相同） 如果根与x的颜色相同，输出根管辖节点数。否则,输出根的后继管辖的节点数。（后继一定与x有相同颜色） */

    #include<cstdio> 
#include<cstring> 
#define g getchar() 
#define lc tr[x].son[0] 
#define rc tr[x].son[1] 
using namespace std; 
const int N=1e5+10; 

struct edge 
{ 
	int y,next; 
}a[N<<1];int last[N],len;//邻接表建边 
void ins(int x,int y) 
{ 
	 a[++len]=(edge){y,last[x]}; 
	 last[x]=len; 
} 

int n,m,col[N],fa[N]; 

struct trnode 
{ 
	int f,u,c,son[2]; 
}; 
struct link_Cut_Tree 
{ 
	trnode tr[N]; 
	inline void update(int x){tr[x].c=tr[lc].c+tr[rc].c+tr[x].u+1;} 
	inline void rotate(int x,int w) 
	{ 
		int f=tr[x].f,ff=tr[f].f,r,R; 
		
		r=tr[x].son[w];R=f; 
		tr[R].son[1-w]=r; 
		if(r!=0)tr[r].f=R; 
		
		r=x;R=ff; 
		     if(tr[R].son[0]==f)tr[R].son[0]=r; 
		else if(tr[R].son[1]==f)tr[R].son[1]=r;//爷爷不一定认这个孩子 
		tr[r].f=R; 
		
		r=f;R=x; 
		tr[R].son[w]=r; 
		tr[r].f=R; 
		
		update(f); 
		update(x); 
	} 
	inline void splay(int x)//把x旋到所属平衡树的根 
	{ 
		while(tr[tr[x].f].son[0]==x||tr[tr[x].f].son[1]==x)//0从来就不认孩子 
		{ 
			int f=tr[x].f,ff=tr[f].f; 
			if(tr[ff].son[0]!=f&&tr[ff].son[1]!=f) 
			{ 
				if(tr[f].son[0]==x)rotate(x,1); 
				else               rotate(x,0); 
			} 
			else 
			{ 
				     if(tr[ff].son[0]==f&&tr[f].son[0]==x)rotate(f,1),rotate(x,1); 
				else if(tr[ff].son[1]==f&&tr[f].son[1]==x)rotate(f,0),rotate(x,0); 
				else if(tr[ff].son[0]==f&&tr[f].son[1]==x)rotate(x,0),rotate(x,1); 
				else                                      rotate(x,1),rotate(x,0); 
			} 
		} 
	} 
	inline void access(int x) 
	{ 
		int y=0; 
		while(x!=0) 
		{ 
			splay(x); 
			tr[x].u+=tr[rc].c-tr[y].c; 
			tr[x].son[1]=y; 
			update(x); 
			y=x;x=tr[x].f; 
		} 
	} 
	inline void link(int x) 
	{ 
		if(!fa[x])return ; 
		int y=fa[x]; 
		access(y);splay(y);splay(x);//x和y还不在一棵树上 
		tr[x].f=y;tr[y].u+=tr[x].c;update(y); 
	} 
	inline void cut(int x) 
	{ 
		if(!fa[x])return ; 
		access(x);splay(x); 
		tr[lc].f=0;lc=0; 
		update(x); 
	} 
	inline int find(int x) 
	{ 
		access(x);splay(x); 
		int y=x; 
		while(tr[y].son[0])y=tr[y].son[0]; 
		splay(y); 
		if(col[x]==col[y])return tr[y].c; 
		else return tr[tr[y].son[1]].c; 
	} 
}LCT[2];//1为黑 

inline void dfs(int x) 
{ 
	for(int k=last[x];k;k=a[k].next) 
	{ 
		int y=a[k].y; 
		if(y!=fa[x]) 
		{ 
			fa[y]=x; 
			LCT[1].link(y); 
			dfs(y); 
		} 
	} 
} 

inline void qr(int &x) 
{ 
	char c=g;x=0; 
	while(!('0'<=c&&c<='9'))c=g; 
	while('0'<=c&&c<='9')x=x*10+c-'0',c=g; 
} 
inline void write(int x) 
{ 
	if(x/10)write(x/10); 
	putchar(x%10+'0'); 
} 

int main() 
{ 
	qr(n); 
	len=0;memset(last,0,sizeof(last)); 
	int x,y; 
	for(int i=1;i<n;i++)qr(x),qr(y),ins(x,y),ins(y,x); 
	for(int i=1;i<=n;i++)LCT[1].tr[i].c=LCT[0].tr[i].c=col[i]=1; 
	dfs(1); 
	qr(m); 
	while(m--) 
	{ 
		qr(y);qr(x); 
		switch(y){ 
			case 0:write(LCT[col[x]].find(x));puts("");break; 
			case 1:LCT[col[x]].cut(x);col[x]^=1;LCT[col[x]].link(x);break; 
		} 
	} 
	return 0; 
}

    chenlibangdn的题解： /这道题还是按照前面QTREE4-5的做法 颜色0/1=黑/白 lsum[x][w]表示这条链下面颜色为w且联通的点的个数 rsum[x][w]表示这条链上面颜色为w且联通的点的个数 c[x]表示点x的儿孙个数 sum[x][w]表示x的儿孙中颜色为w的个数 然后仿照前面的维护一下就好了。/

    #include<cstdio> 
#include<cstring> 
#include<iostream> 
#include<cmath> 
#include<algorithm> 
using namespace std; 
template<typename T>inline void qr(T &x){ 
    x=0;int f=0;char s=getchar(); 
    while(s<'0'||'9'<s)f|=s=='-',s=getchar(); 
    while('0'<=s&&s<='9')x=x*10+s-48,s=getchar(); 
    x=f?-x:x; 
} 
const int mxn=1e5+10; 
int n,col[mxn]; 
int tot,hd[mxn],ver[mxn],nxt[mxn]; 
int fa[mxn],c[mxn],sum[mxn][2],lsum[mxn][2],rsum[mxn][2]; 
int a[mxn][2],ch[mxn][2]; 
#define lc ch[x][0] 
#define rc ch[x][1] 
#define ls(x) ch[x][0] 
#define rs(x) ch[x][1] 
#define rep for(int w=0;w<=1;w++) 
#define okl (col[x]==w)*(c[lc]==sum[lc][w]) 
#define okr (col[x]==w)*(c[rc]==sum[rc][w]) 
bool nrt(int x){return ls(fa[x])==x||rs(fa[x])==x;} 
void update(int x){ 
    c[x]=c[lc]+c[rc]+1; 
    rep sum[x][w]=sum[lc][w]+sum[rc][w]+(col[x]==w); 
    rep lsum[x][w]=lsum[rc][w]+okr*(1+a[x][w]+lsum[lc][w]); 
    rep rsum[x][w]=rsum[lc][w]+okl*(1+a[x][w]+rsum[rc][w]); 
} 
void rotate(int x){ 
    int y=fa[x],z=fa[y],w=rs(y)==x; 
    if(nrt(y))ch[z][rs(z)==y]=x;fa[x]=z; 
    fa[ch[y][w]=ch[x][1-w]]=y; 
    ch[x][1-w]=y,fa[y]=x; 
    update(y); 
} 
void splay(int x){ 
    while(nrt(x)){ 
        int y=fa[x],z=fa[y]; 
        if(nrt(y)) 
            (rs(z)==y)^(rs(y)==x)?rotate(x):rotate(y); 
        rotate(x); 
    } 
    update(x); 
} 
void access(int x){ 
    for(int y=0;x;x=fa[y=x]){ 
        splay(x); 
        if(y) rep a[x][w]-=rsum[y][w]; 
        if(rc) rep a[x][w]+=rsum[rc][w]; 
        rc=y;update(x); 
    } 
} 
void modify(int x){ 
    access(x); 
    splay(x);col[x]=1-col[x]; 
    update(x); 
} 
int query(int x){ 
    access(x); 
    splay(x); 
    return 1+a[x][col[x]]+lsum[lc][col[x]]+rsum[rc][col[x]]; 
} 
void add(int x,int y){ 
    ver[++tot]=y;nxt[tot]=hd[x];hd[x]=tot; 
} 
void maketree(int x){ 
    for(int i=hd[x];i;i=nxt[i]){ 
        int y=ver[i]; 
        if(y==fa[x])continue; 
        fa[y]=x; 
        maketree(y); 
        rep a[x][w]+=a[y][w]+(col[y]==w); 
    } 
    update(x); 
} 
int main(){ 
    qr(n); 
    for(int i=1;i<n;i++){ 
        int x,y;qr(x),qr(y); 
        add(x,y),add(y,x); 
    } 
    maketree(1); 
    int m;qr(m); 
    while(m--){ 
        int x,op; 
        qr(op),qr(x); 
        if(op)modify(x); 
        else printf("%d\n",query(x)); 
    } 
    return 0; 
}
    • 0
      @ 2025-10-8 16:51:59

      lzy:

      /*
思路：	        我们要把点的颜色转换成连向父节点的边的颜色，这样每次换颜色就只用处理与一条边的关系，不这样做我们就会被菊花图卡。
		所以我们就必须维护有根树（根不能换），不能用makeroot来改变树的形状。
		我们定义两棵树，一棵为为黑，一棵为白，每个点会同时在两棵树出现。
		因为对于一个有色联通块(树)，只有根的父亲的颜色与其他点的父亲的颜色不同。 (联通块的根为1时需要特判) 
		所以我们每次换颜色只处理一条边的在两棵树上的断（连）就行了。 (一个联通块就是边越来越多，最后汇合而成的)（理由有点牵强，但本题本来就不好讲）
		重点在于查询——LCT所维护的森林的每棵树的节点的深度要保证严格递增，但是在树上的联通块的节点可能深度一样。那怎么办呢？
		我们在splay节点(trnode)多定义一个变量u，表示其他子树节点的总数——因为父亲只认得两个孩子（悲催的家庭）,这样我们就能保证正确性了。
		全局(原树)的根设为1。
		查询时，我们把x(询问的元素)access并splay上去，再一直往左儿子跳，找到根(不是全局的)。因为根的颜色可能与x同，也可能不同。（只有根为1时，根的颜色才有可能与x的颜色相同）
		如果根与x的颜色相同，输出根管辖的节点数。否则，输出根的后继管辖的节点数。（后继一定与x有相同颜色）
*/ 
#include<cstdio>
#include<cstring>
#define g getchar()
#define lc tr[x].son[0]
#define rc tr[x].son[1]
using namespace std;
const int N=1e5+10;

struct edge
{
	int y,next;
}a[N<<1];int last[N],len;//邻接表建边
void ins(int x,int y)
{
	 a[++len]=(edge){y,last[x]};
	 last[x]=len;
}

int n,m,col[N],fa[N];

struct trnode
{
	int f,u,c,son[2];
};
struct link_Cut_Tree
{
	trnode tr[N];
	inline void update(int x){tr[x].c=tr[lc].c+tr[rc].c+tr[x].u+1;}
	inline void rotate(int x,int w)
	{
		int f=tr[x].f,ff=tr[f].f,r,R;
		
		r=tr[x].son[w];R=f;
		tr[R].son[1-w]=r;
		if(r!=0)tr[r].f=R;
		
		r=x;R=ff;
		     if(tr[R].son[0]==f)tr[R].son[0]=r;
		else if(tr[R].son[1]==f)tr[R].son[1]=r;//爷爷不一定认这个孩子
		tr[r].f=R;
		
		r=f;R=x;
		tr[R].son[w]=r;
		tr[r].f=R;
		
		update(f);
		update(x);
	}
	inline void splay(int x)//把x旋到所属平衡树的根 
	{
		while(tr[tr[x].f].son[0]==x||tr[tr[x].f].son[1]==x)//0从来就不认孩子
		{
			int f=tr[x].f,ff=tr[f].f;
			if(tr[ff].son[0]!=f&&tr[ff].son[1]!=f)
			{
				if(tr[f].son[0]==x)rotate(x,1);
				else               rotate(x,0);
			}
			else
			{
				     if(tr[ff].son[0]==f&&tr[f].son[0]==x)rotate(f,1),rotate(x,1);
				else if(tr[ff].son[1]==f&&tr[f].son[1]==x)rotate(f,0),rotate(x,0);
				else if(tr[ff].son[0]==f&&tr[f].son[1]==x)rotate(x,0),rotate(x,1);
				else                                      rotate(x,1),rotate(x,0);
			}
		}
	}
	inline void access(int x)
	{
		int y=0;
		while(x!=0)
		{
			splay(x);
			tr[x].u+=tr[rc].c-tr[y].c;
			tr[x].son[1]=y;
			update(x);
			y=x;x=tr[x].f;
		}
	}
	inline void link(int x)
	{
		if(!fa[x])return ;
		int y=fa[x];
		access(y);splay(y);splay(x);//x和y还不在一棵树上。为什么x不用access呢？因为x还未向原树的父亲连边，x为所属splay中深度最小的点，整棵splay的根的父亲为0。
		tr[x].f=y;tr[y].u+=tr[x].c;update(y);
	}
	inline void cut(int x)
	{
		if(!fa[x])return ;
		access(x);splay(x);//y一定在x的左子树内。因为之前tr[x].f=y，使得access时一定能遍历到fa[x]。 
		tr[lc].f=0;lc=0;//直接断开与父亲那一边的联系,tr[x].son[0]不一定为fa[x]，但没关系.
		update(x);
	}
	inline int find(int x)
	{
		access(x);splay(x);
		int y=x;
		while(tr[y].son[0])y=tr[y].son[0];
		splay(y);
		if(col[x]==col[y])return tr[y].c;
		else return tr[tr[y].son[1]].c;
	}
}LCT[2];//1为黑

inline void dfs(int x)
{
	for(int k=last[x];k;k=a[k].next)
	{
		int y=a[k].y;
		if(y!=fa[x])
		{
			fa[y]=x;
			LCT[1].link(y);
			dfs(y);
		}
	}
}

inline void qr(int &x)
{
	char c=g;x=0;
	while(!('0'<=c&&c<='9'))c=g;
	while('0'<=c&&c<='9')x=x*10+c-'0',c=g;
}
inline void write(int x)
{
	if(x/10)write(x/10);
	putchar(x%10+'0');
}

int main()
{
	qr(n);
	len=0;memset(last,0,sizeof(last));
	int x,y;
	for(int i=1;i<n;i++)qr(x),qr(y),ins(x,y),ins(y,x);
	for(int i=1;i<=n;i++)LCT[1].tr[i].c=LCT[0].tr[i].c=col[i]=1;
	dfs(1);
	qr(m);
	while(m--)
	{
		qr(y);qr(x);
		switch(y){
			case 0:write(LCT[col[x]].find(x));puts("");break;
			case 1:LCT[col[x]].cut(x);col[x]^=1;LCT[col[x]].link(x);break;
		}
	}
	return 0;
}

      chenlibangdn:

      /*这道题还是按照前面QTREE4-5的做法
颜色0/1=黑/白
lsum[x][w]表示这条链下面颜色为w且联通的点的个数
rsum[x][w]表示这条链上面颜色为w且联通的点的个数
c[x]表示点x的儿孙个数
sum[x][w]表示x的儿孙中颜色为w的个数
然后仿照前面的维护一下就好了。*/

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
template<typename T>inline void qr(T &x){
	x=0;int f=0;char s=getchar();
	while(s<'0'||'9'<s)f|=s=='-',s=getchar();
	while('0'<=s&&s<='9')x=x*10+s-48,s=getchar();
	x=f?-x:x;
}
const int mxn=1e5+10;
int n,col[mxn];
int tot,hd[mxn],ver[mxn],nxt[mxn];
int fa[mxn],c[mxn],sum[mxn][2],lsum[mxn][2],rsum[mxn][2];
int a[mxn][2],ch[mxn][2];
#define lc ch[x][0]
#define rc ch[x][1]
#define ls(x) ch[x][0]
#define rs(x) ch[x][1]
#define rep for(int w=0;w<=1;w++)
#define okl (col[x]==w)*(c[lc]==sum[lc][w])
#define okr (col[x]==w)*(c[rc]==sum[rc][w])
bool nrt(int x){return ls(fa[x])==x||rs(fa[x])==x;}
void update(int x){
	c[x]=c[lc]+c[rc]+1;
	rep sum[x][w]=sum[lc][w]+sum[rc][w]+(col[x]==w);
	rep lsum[x][w]=lsum[rc][w]+okr*(1+a[x][w]+lsum[lc][w]);
	rep rsum[x][w]=rsum[lc][w]+okl*(1+a[x][w]+rsum[rc][w]);
}
void rotate(int x){
	int y=fa[x],z=fa[y],w=rs(y)==x;
	if(nrt(y))ch[z][rs(z)==y]=x;fa[x]=z;
	fa[ch[y][w]=ch[x][1-w]]=y;
	ch[x][1-w]=y,fa[y]=x;
	update(y);
}
void splay(int x){
	while(nrt(x)){
		int y=fa[x],z=fa[y];
		if(nrt(y))
			(rs(z)==y)^(rs(y)==x)?rotate(x):rotate(y);
		rotate(x);
	}
	update(x);
}
void access(int x){
	for(int y=0;x;x=fa[y=x]){
		splay(x);
		if(y) rep a[x][w]-=rsum[y][w];
		if(rc) rep a[x][w]+=rsum[rc][w];
		rc=y;update(x);
	}
}
void modify(int x){
	access(x);
	splay(x);
	col[x]=1-col[x];
	update(x);
}
int query(int x){
	access(x);
	splay(x);
	return 1+a[x][col[x]]+lsum[lc][col[x]]+rsum[rc][col[x]];
}
void add(int x,int y){
	ver[++tot]=y;
	nxt[tot]=hd[x];
	hd[x]=tot;
}
void maketree(int x){
	for(int i=hd[x];i;i=nxt[i]){
		int y=ver[i];
		if(y==fa[x])continue;
		fa[y]=x;
		maketree(y);
		rep a[x][w]+=a[y][w]+(col[y]==w);
	}
	update(x);
}
int main(){
	qr(n);
	for(int i=1;i<n;i++){
		int x,y;qr(x),qr(y);
		add(x,y),add(y,x);
	}
	maketree(1);
	int m;qr(m);
	while(m--){
		int x,op;
		qr(op),qr(x);
		if(op)modify(x);
		else printf("%d\n",query(x));
	}
	return 0;
}
      • 1

      Qtree6 加强版

      信息

      ID
      550
      时间
      1000ms
      内存
      2048MiB
      难度
      10
      标签
      递交数
      49
      已通过
      1
      上传者
      1. Language
      2. 兼容模式
      3. 主题
      3. Worker 0, 6ms
      4. Powered by Hydro v5.0.1 Community