#include <cstdio>#include <cstring>#include <iostream>#define isr(A)	(s[s[A].fa].ch[0]!=A&&s[s[A].fa].ch[1]!=A)using namespace std;const int maxn=10010;int n,m;struct NODE{	int ch[2],fa,rev;	}s[10010];char str[20];void pushdown(int x){	if(s[x].rev)	{		swap(s[x].ch[0],s[x].ch[1]);		if(s[x].ch[0])	s[s[x].ch[0]].rev^=1;		if(s[x].ch[1])	s[s[x].ch[1]].rev^=1;		s[x].rev=0;	}}void rotate(int x){	int y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]);	if(!isr(y))	s[z].ch[y==s[z].ch[1]]=x;	s[y].ch[d]=s[x].ch[d^1],s[y].fa=x,s[x].fa=z;	if(s[x].ch[d^1])	s[s[x].ch[d^1]].fa=y;	s[x].ch[d^1]=y;}void pd(int x){if(!isr(x))	pd(s[x].fa);	pushdown(x);}void splay(int x){	pd(x);	while(!isr(x))	{		int y=s[x].fa,z=s[y].fa;		if(!isr(y))		{			if((x==s[y].ch[1])^(y==s[z].ch[1]))	rotate(x);			else	rotate(y);		}		rotate(x);	}}void access(int x){	int y=0;	while(x)	splay(x),s[x].ch[1]=y,y=x,x=s[x].fa;}void maker(int x){	access(x),splay(x),s[x].rev^=1;}int findr(int x){	access(x),splay(x);	while(s[x].ch[0])	pushdown(x),x=s[x].ch[0];	return x;}void link(int x,int y){	maker(x),s[x].fa=y;}void cut(int x,int y){	maker(y),access(x),splay(x);	s[x].ch[0]=s[y].fa=0;}int rd(){	int ret=0;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	gc=getchar();	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret;}int main(){	n=rd(),m=rd();	int i,a,b;	for(i=1;i<=m;i++)	{		scanf("%s",str);		a=rd(),b=rd();		switch(str[0])		{			case ‘D‘:cut(a,b);	break;			case ‘C‘:link(a,b);	break;			case ‘Q‘:if(findr(a)==findr(b))	printf("Yes\n");			else	printf("No\n");		}	}	return 0;}

#include <cstdio>#include <cstring>#include <iostream>#define isr(A)	(s[s[A].fa].ch[0]!=A&&s[s[A].fa].ch[1]!=A)#define mod 51061using namespace std;typedef unsigned int ui;struct node{	ui ch[2],fa,rev;	ui ts,tc,sum,siz,v;	void C(ui x)	{v=v*x%mod,sum=sum*x%mod,tc=tc*x%mod,ts=ts*x%mod;}	void S(ui x)	{v=(v+x)%mod,sum=(sum+siz*x)%mod,ts=(ts+x)%mod;}}s[100010];char str[10];ui n,m;void pushup(ui x){	s[x].siz=s[s[x].ch[0]].siz+s[s[x].ch[1]].siz+1;	s[x].sum=(s[s[x].ch[0]].sum+s[s[x].ch[1]].sum+s[x].v)%mod;}void pushdown(ui x){	if(s[x].rev)	{		swap(s[x].ch[0],s[x].ch[1]);		if(s[x].ch[0])	s[s[x].ch[0]].rev^=1;		if(s[x].ch[1])	s[s[x].ch[1]].rev^=1;		s[x].rev=0;	}	if(s[x].tc!=1)	{		if(s[x].ch[0])	s[s[x].ch[0]].C(s[x].tc);		if(s[x].ch[1])	s[s[x].ch[1]].C(s[x].tc);		s[x].tc=1;	}	if(s[x].ts)	{		if(s[x].ch[0])	s[s[x].ch[0]].S(s[x].ts);		if(s[x].ch[1])	s[s[x].ch[1]].S(s[x].ts);		s[x].ts=0;	}}void rotate(ui x){	ui y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]);	if(!isr(y))	s[z].ch[y==s[z].ch[1]]=x;	s[y].ch[d]=s[x].ch[d^1],s[x].fa=z,s[y].fa=x;	if(s[x].ch[d^1])	s[s[x].ch[d^1]].fa=y;	s[x].ch[d^1]=y;	pushup(y),pushup(x);}void updata(ui x){	if(!isr(x))	updata(s[x].fa);	pushdown(x);}void splay(ui x){	updata(x);	while(!isr(x))	{		ui y=s[x].fa,z=s[y].fa;		if(!isr(y))		{			if((x==s[y].ch[0])^(y==s[z].ch[0]))	rotate(x);			else	rotate(y);		}		rotate(x);	}}void access(ui x){	ui y=0;	while(x)	splay(x),s[x].ch[1]=y,pushup(x),y=x,x=s[x].fa;}void maker(ui x){	access(x),splay(x),s[x].rev^=1;}void cut(ui x,ui y){	maker(y),access(x),splay(x);	s[x].ch[0]=s[y].fa=0,pushup(x);}void link(ui x,ui y){	maker(y),s[y].fa=x;}ui rd(){	ui ret=0;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	gc=getchar();	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret;}int main(){	n=rd(),m=rd();	ui i,a,b,c,d;	for(i=1;i<=n;i++)	s[i].v=1;	for(i=1;i<n;i++)	link(rd(),rd());	for(i=1;i<=m;i++)	{		scanf("%s",str),a=rd(),b=rd();		switch(str[0])		{			case ‘*‘:c=rd(),maker(a),access(b),splay(b),s[b].C(c);	break;			case ‘+‘:c=rd(),maker(a),access(b),splay(b),s[b].S(c);	break;			case ‘-‘:c=rd(),d=rd(),cut(a,b),link(c,d);	break;			case ‘/‘:maker(a),access(b),splay(b),printf("%u\n",s[b].sum);	break;		}	}	return 0;}

#include <cstdio>#include <iostream>#include <cstring>#define isr(A)	(s[s[A].fa].ch[0]!=A&&s[s[A].fa].ch[1]!=A)using namespace std;int n,m;struct node{	int ch[2],fa,sum,v,rev;}s[300010];void pushup(int x){	s[x].sum=s[s[x].ch[0]].sum^s[s[x].ch[1]].sum^s[x].v;}void pushdown(int x){	if(s[x].rev)	{		swap(s[x].ch[0],s[x].ch[1]);		if(s[x].ch[0])	s[s[x].ch[0]].rev^=1;		if(s[x].ch[1])	s[s[x].ch[1]].rev^=1;		s[x].rev=0;	}}void rotate(int x){	int y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]);	if(!isr(y))	s[z].ch[y==s[z].ch[1]]=x;	s[x].fa=z,s[y].fa=x,s[y].ch[d]=s[x].ch[d^1];	if(s[x].ch[d^1])	s[s[x].ch[d^1]].fa=y;	s[x].ch[d^1]=y;	pushup(y),pushup(x);}void updata(int x){	if(!isr(x))	updata(s[x].fa);	pushdown(x);}void splay(int x){	updata(x);	while(!isr(x))	{		int y=s[x].fa,z=s[y].fa;		if(!isr(y))		{			if((x==s[y].ch[0])^(y==s[z].ch[0]))	rotate(x);			else	rotate(y);		}		rotate(x);	}}void access(int x){	int y=0;	while(x)	splay(x),s[x].ch[1]=y,pushup(x),y=x,x=s[x].fa;}void maker(int x){	access(x),splay(x),s[x].rev^=1;}void cut(int x,int y){	maker(x),access(y),splay(y);	if(s[x].fa==y)	s[x].fa=s[y].ch[0]=0,pushup(y);}void link(int x,int y){	maker(x),s[x].fa=y;}void split(int a,int b){	maker(a),access(b),splay(b);}int findr(int x){	access(x),splay(x);	while(s[x].ch[0])	x=s[x].ch[0];	return x;}int rd(){	int ret=0;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	gc=getchar();	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret;}int main(){	n=rd(),m=rd();	int i,a,b,c;	for(i=1;i<=n;i++)	s[i].sum=s[i].v=rd();	for(i=1;i<=m;i++)	{		c=rd(),a=rd(),b=rd();		switch(c)		{			case 0:split(a,b),printf("%d\n",s[b].sum);	break;			case 1:if(findr(a)!=findr(b))	link(a,b);	break;			case 2:cut(a,b);	break;			case 3:splay(a),s[a].v=b,pushup(a);	break;		}	}	return 0;}

#include <cstdio>#include <cstring>#include <iostream>#define isr(A)	(s[s[A].fa].ch[0]!=A&&s[s[A].fa].ch[1]!=A)using namespace std;int n,m;struct node{	int ch[2],fa,sum,v,rev;}s[30010];char str[20];void pushup(int x){	s[x].sum=s[s[x].ch[0]].sum+s[s[x].ch[1]].sum+s[x].v;}void pushdown(int x){	if(s[x].rev)	{		swap(s[x].ch[0],s[x].ch[1]);		if(s[x].ch[0])	s[s[x].ch[0]].rev^=1;		if(s[x].ch[1])	s[s[x].ch[1]].rev^=1;		s[x].rev=0;	}}void rotate(int x){	int y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]);	if(!isr(y))	s[z].ch[y==s[z].ch[1]]=x;	s[y].fa=x,s[x].fa=z,s[y].ch[d]=s[x].ch[d^1];	if(s[x].ch[d^1])	s[s[x].ch[d^1]].fa=y;	s[x].ch[d^1]=y;	pushup(y),pushup(x);}void updata(int x){	if(!isr(x))	updata(s[x].fa);	pushdown(x);}void splay(int x){	updata(x);	while(!isr(x))	{		int y=s[x].fa,z=s[y].fa;		if(!isr(y))		{			if((x==s[y].ch[0])^(y==s[z].ch[0]))	rotate(x);			else	rotate(y);		}		rotate(x);	}}void access(int x){	int y=0;	while(x)	splay(x),s[x].ch[1]=y,pushup(x),y=x,x=s[x].fa;}void maker(int x){	access(x),splay(x),s[x].rev^=1;}void link(int x,int y){	maker(x),s[x].fa=y;}int findr(int x){	access(x),splay(x);	while(s[x].ch[0])	x=s[x].ch[0];	return x;}void split(int x,int y){	maker(y),access(x),splay(x);}int rd(){	int ret=0;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	gc=getchar();	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret;}int main(){	n=rd();	int i,a,b,c;	for(i=1;i<=n;i++)	s[i].sum=s[i].v=rd();	m=rd();	for(i=1;i<=m;i++)	{		scanf("%s",str),a=rd(),b=rd();		switch(str[0])		{			case ‘b‘:if(findr(a)!=findr(b))	printf("yes\n"),link(a,b);					else	printf("no\n");	break;			case ‘p‘:splay(a),s[a].v=b,pushup(a);	break;			case ‘e‘:if(findr(a)!=findr(b))	printf("impossible\n");					else	split(a,b),printf("%d\n",s[a].sum);	break;		}	}	return 0;}