Lvat_s Blog

区间DP

离散化后考虑一段区间(l,r)（这里指的是出现时间的区间）

那么这段区间的R的最小值至少为这一段区间最高的线段（感觉讲的很抽象啊……最高的线段高度等于这个外星人离你的距离）

然后输出(0,tb)表示在[1,tb-1]能取到的最小代价，所以中间那个tb要++，因为我用的是开区间

#include<cstdio>
#include<algorithm>
using namespace std;

int n,table[10005],tb,f[1005][1005],T;

struct Plane{
int a,b,d;
}p[305];

int main(){
freopen("3928_4048.in","r",stdin);
freopen("3928_4048.out","w",stdout);
scanf("%d",&T);
while(T--){
    tb=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d %d %d",&p[i].a,&p[i].b,&p[i].d);
        table[++tb]=p[i].a;
        table[++tb]=p[i].b;
    }
    sort(table+1,table+tb+1);
    tb=unique(table+1,table+tb+1)-table-1;
    for(int i=1;i<=n;i++){
        p[i].a=lower_bound(table+1,table+tb+1,p[i].a)-table;
        p[i].b=lower_bound(table+1,table+tb+1,p[i].b)-table;
    }
    tb++;
    for(int len=0;len<=tb;len++){
        for(int i=0;i<=tb-len;i++){
            int j=i+len,H=-1;
            for(int k=1;k<=n;k++){
                if(i<p[k].a && p[k].b<j && (H==-1 || p[H].d<p[k].d))H=k;
            }
            if(H==-1)f[i][j]=0;
            else {
                f[i][j]=2100000000;
                for(int k=p[H].a;k<=p[H].b;k++){
                    f[i][j]=min(f[i][j],f[i][k]+f[k][j]+p[H].d);
                }
            }
        }
    }
    printf("%d\n",f[0][tb]);
}
return 0;
}

三分点在AB和CD上面的位置

然后搞一搞就行了

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

struct Point{
double x,y;
Point(double _x=0,double _y=0):x(_x),y(_y){}
friend Point operator+(Point a,Point b){return Point(a.x+b.x,a.y+b.y);}
friend Point operator-(Point a,Point b){return Point(a.x-b.x,a.y-b.y);}
friend Point operator*(Point a,double k){return Point(a.x*k,a.y*k);}
double mold(){return sqrt(x*x+y*y);}
}A,B,C,D;

double V0,Vab,Vcd;
const double eps=1e-6;

double Calc(Point X,Point Y){
return (Y-X).mold()/V0+(Y-D).mold()/Vcd;
}

double sanfen2(Point x){
double l=0,r=1,res=(x-A).mold()/Vab;
while(r-l>eps){
	double mid1=l+(r-l)/3.0,mid2=r-(r-l)/3.0;
	double p1=Calc(x,C+(D-C)*mid1),p2=Calc(x,C+(D-C)*mid2);
	if(p1<p2)r=mid2;
	else l=mid1;
}
return res+Calc(x,C+(D-C)*l);
}

double sanfen1(){
double l=0,r=1;
while(r-l>eps){
	double mid1=l+(r-l)/3.0,mid2=r-(r-l)/3.0;
	double p1=sanfen2(A+(B-A)*mid1),p2=sanfen2(A+(B-A)*mid2);
	if(p1<p2)r=mid2;
	else l=mid1;
}
return sanfen2(A+(B-A)*l);
}

int main(){
freopen("1857.in","r",stdin);
freopen("1857.out","w",stdout);
scanf("%lf %lf %lf %lf %lf %lf %lf %lf",&A.x,&A.y,&B.x,&B.y,&C.x,&C.y,&D.x,&D.y);
scanf("%lf %lf %lf",&Vab,&Vcd,&V0);
printf("%.2lf\n",sanfen1());
return 0;
}

状态压缩DP

根据期望的线性性，我们知道可以分开考虑每个物品在每一时刻出现的期望

然后把这些期望加起来再除以物品种类数（因为要求平均期望，而每种物品出现的概率都是1/k）

那么DP方程就是

f[i][j]+=max(f[i+1][j],f[i+1][j|bit[k]]+score[k]);(其中满足可以取k物品的条件)

f[i][j]+=f[i+1][j];(当前枚举到的k物品没办法取到所得到的上一次的平均得分期望)

最后f[i][j]/=k就可以了

为什么要从f[i+1][j]推导f[i][j]?因为如果顺推的话有可能会枚举到无效的状态，而且最后没办法输出f[n][j]

所以只需要倒推就可以解决问题啦

#include<cstdio>
#include<algorithm>
using namespace std;

int k,n,bit[25],ist[25],score[25];
double f[105][1<<15];

int main(){
freopen("1076.in","r",stdin);
freopen("1076.out","w",stdout);
scanf("%d %d",&n,&k);
for(int i=1;i<=20;i++)bit[i]=1<<(i-1);
for(int i=1;i<=k;i++){
	scanf("%d",&score[i]);
	int tp;
	for(int j=0;scanf("%d",&tp),tp;j++){
		ist[i]|=bit[tp];
	}
}
for(int i=n;i>=1;i--){
	for(int j=0;j<=bit[k+1]-1;j++){
		for(int l=1;l<=k;l++){
			if((j&ist[l])==ist[l]){
				f[i][j]+=max(f[i+1][j],f[i+1][j|bit[l]]+score[l]);
			}
			else f[i][j]+=f[i+1][j];
		}
		f[i][j]/=k;
	}
}
printf("%.6f\n",f[1][0]);
return 0;
}

排序直接做就行了

#include<cstdio>
#include<algorithm>
using namespace std;

int n,ans=0;

struct Event{
int s,t;
friend bool operator<(Event a,Event b){
return (a.t<b.t)||(a.t==b.t && a.s<b.s);
}
}e[10005];

int main(){
freopen("1664.in","r",stdin);
freopen("1664.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
	scanf("%d %d",&e[i].s,&e[i].t);
	e[i].t+=e[i].s;
}
sort(e+1,e+n+1);
int last=0;
for(int i=1;i<=n;i++){
	if(e[i].s>=e[last].t){
		ans++;
		last=i;
	}
	else if(e[i].t<e[last].t){
		last=i;
	}
}
printf("%d\n",ans);
return 0;
}

水题

以后交题目一定要检查调试有没有删掉

因为这个WA了一次……

简单的单调栈

#include<cstdio>
#include<stack>
using namespace std;

stack<int> S;

int n,w,ans,f[500005]={0};

int main(){
freopen("1683.in","r",stdin);
freopen("1683.out","w",stdout);
scanf("%d %d",&n,&w);
for(int i=1;i<=n;i++){
	int tpa,tpb;
	scanf("%d %d",&tpa,&tpb);
	int last=-1;
	while(!S.empty() && S.top()>tpb){int res=S.top();S.pop();if(res!=last){ans++;last=res;}}
	S.push(tpb);
}
while(!S.empty()){
	if(f[S.top()]==0 && S.top()){
		f[S.top()]++;
		ans++;
	}
	S.pop();
}
printf("%d\n",ans);
return 0;
}

事实证明Lvat_s就是一个sb。。。

这题调试了2天

其实死在了一个很明显的错误上面

在倒数第二个关于q的循环里，我写道：

if(reans>e[i].v){……}

此时i明明表示q好不好……

正确的写法是：

if(reans>e[ask[i].ans].v){……}

还是贴一下代码吧，跑得很慢（19104ms）

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int n,m,q,f[100005];

void Read(int &x){
char ch;
while((ch=getchar())<'0' || ch>'9');
x=ch-'0';
while((ch=getchar())>='0' && ch<='9')x=x*10+ch-'0';
}

struct Node{
int v,mx,rev,id;
Node *ch[2],*fa,*mxe;
Node(int val,Node *fat);
void Pushdown();
void Pushup();
}*root[1100005],*Null;

Node::Node(int val,Node *fat){
ch[0]=ch[1]=Null;
if(val)mxe=this;
else mxe=Null;
fa=fat;
v=mx=val;
rev=id=0;
}

void Node::Pushdown(){
if(rev){
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
    swap(ch[0]->ch[0],ch[0]->ch[1]);
    swap(ch[1]->ch[0],ch[1]->ch[1]);
    rev=0;
}
}

void Node::Pushup(){
mx=v;
if(v)mxe=this;
else mxe=Null;
if(ch[0]!=Null && ch[0]->mx>mx){mx=ch[0]->mx;mxe=ch[0]->mxe;}
if(ch[1]!=Null && ch[1]->mx>mx){mx=ch[1]->mx;mxe=ch[1]->mxe;}
}

int Notroot(Node *p){
return (p->fa->ch[0]==p)||(p->fa->ch[1]==p);
}

void Prepare(Node *p){
if(Notroot(p))Prepare(p->fa);
p->Pushdown();
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y))Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
}

void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}
}

void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
swap(x->ch[0],x->ch[1]);
}

void Link(Node *x,Node *y){
Makeroot(x);
x->fa=y;
}

void Cut(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
if(y->ch[0]==x){y->ch[0]=Null;x->fa=Null;}
}

int GetMx(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
return y->mx;
}

Node *MxAddress(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
return y->mxe;
}

Node *GetNull(){
Node *p=new Node(0,Null);
p->fa=p->ch[0]=p->ch[1]=p->mxe=p;
p->v=p->mx=-2100000000;
p->rev=p->id=0;
return p;
}

Node *ToLct(int x){
return root[x];
}

struct Edge{
int a,b,v,id,del;
friend bool operator<(Edge a,Edge b){
return (a.a<b.a)||(a.a==b.a && a.b<b.b);
}
}e[1000005];

bool cmp1(Edge a,Edge b){
return a.v<b.v;
}

bool cmp2(Edge a,Edge b){
return a.id<b.id;
}

struct Ask{
int k,x,y,ans;
}ask[100005];

int Div(int x,int y){
int l=1,r=m;
while(l<=r){
	int mid=(l+r)>>1;
	if(e[mid].a==x && e[mid].b==y)return mid;
	if(e[mid].a<x || (e[mid].a==x && e[mid].b<y)){l=mid+1;}
	else r=mid-1;
}
return (l+r)>>1;
}

int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int x,int y){if(x<y)f[y]=x;else f[x]=y;}

int main(){
freopen("2594.in","r",stdin);
freopen("2594.out","w",stdout);
Read(n);Read(m);Read(q);
Null=GetNull();
for(int i=1;i<=m;i++){
	Read(e[i].a);Read(e[i].b);Read(e[i].v);
	if(e[i].a>e[i].b)swap(e[i].a,e[i].b);
}
sort(e+1,e+m+1,cmp1);
for(int i=1;i<=n;i++)root[i]=new Node(0,Null);
for(int i=1;i<=m;i++){
	e[i].id=i;
	root[i+n]=new Node(e[i].v,Null);
}
sort(e+1,e+m+1);
for(int i=1;i<=q;i++){
	Read(ask[i].k);
	Read(ask[i].x);
	Read(ask[i].y);
	if(ask[i].x>ask[i].y)swap(ask[i].x,ask[i].y);
	if(ask[i].k==2){
		int sci=Div(ask[i].x,ask[i].y);
		ask[i].ans=e[sci].id;
		e[sci].del=1;
	}
}
sort(e+1,e+m+1,cmp2);
for(int i=1;i<=n;i++)f[i]=i;
int tot=0;
for(int i=1;i<=m;i++){
	root[i+n]->id=i;
	if(!e[i].del && Find(e[i].a)!=Find(e[i].b)){
		Union(Find(e[i].a),Find(e[i].b));
		Link(ToLct(e[i].a),ToLct(i+n));
		Link(ToLct(e[i].b),ToLct(i+n));
		tot++;
		if(tot==n-1)break;
	}
}
for(int i=q;i>=1;i--){
	if(ask[i].k==1){
		ask[i].ans=GetMx(ToLct(ask[i].x),ToLct(ask[i].y));
	}
	else {
		Node *mx=MxAddress(ToLct(ask[i].x),ToLct(ask[i].y));
		int reans=mx->mx;
		if(reans>e[ask[i].ans].v){
			Cut(ToLct(e[mx->id].a),mx);
			Cut(ToLct(e[mx->id].b),mx);
			Link(ToLct(ask[i].x),ToLct(ask[i].ans+n));
			Link(ToLct(ask[i].y),ToLct(ask[i].ans+n));
		}
	}
}
for(int i=1;i<=q;i++){
	if(ask[i].k==1)printf("%d\n",ask[i].ans);
}
return 0;
}

最近感觉状态差极了

这种题要调40min……

UR水题不会做

以我3个月前的水平反而会了

感觉极其不爽，为什么有些人没有你努力竞赛照样比你搞得好那是因为这些人太假了，刷题都用小号给你造成不怎么刷题的假象(2016.3.10才发现……)

我觉得这和智商没什么关系

不说了，这是一个裸并查集

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int n,f[300005],is[300005],stx[555];

struct Read{
int opt,v,ans;
}read[100005];

int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int sa,int sb){if(sa<sb)f[sa]=sb;else f[sb]=sa;}

int main(){
freopen("4320.in","r",stdin);
freopen("4320.out","w",stdout);
scanf("%d",&n);
memset(stx,127,sizeof(stx));
for(int i=1;i<=n;i++){
	char s[10];
	int val;
	scanf("%s %d",s,&val);
	read[i].opt=s[0]-'A';
	read[i].v=val;
	if(read[i].opt==0){
		for(int j=1;j<=550;j++)stx[j]=min(stx[j],val%j);
		is[val]=1;
	}
	else if(val<=550){
		read[i].ans=stx[val];
	}
}
f[300001]=300001;
for(int i=300000;i>=1;i--){if(!is[i])f[i]=Find(f[i+1]);else f[i]=i;}
for(int i=n;i>=1;i--){
	if(read[i].opt==0){
		Union(Find(read[i].v),Find(read[i].v+1));
	}
	else if(read[i].v>550){
		read[i].ans=2100000000;
		for(int j=0;j*read[i].v<=300000;j++){
			read[i].ans=min(read[i].ans,(Find(read[i].v*j==0?1:read[i].v*j)==300001?read[i].v-1:Find(read[i].v*j==0?1:read[i].v*j))%read[i].v);
		}
	}
}
for(int i=1;i<=n;i++){
	if(read[i].opt)printf("%d\n",read[i].ans);
}
return 0;
}

状压DP

f[i][j][k]表示当前在第i行，包括第i行一共放了j个国王，而且这一行状态为k的方案数

那么f[i][j][k]=Sigma(f[i-1][j-cnt[l]][l],其中l为一种可行方案且不和k状态冲突)

然后搞个ans加一下就没了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

long long n,K,cnt[1<<10],f[15][105][1<<10],rule[1<<10],ed,ans;

int Cnt(int s){
int ans=0;
while(s){
	ans+=s&1;
	s>>=1;
}
return ans;
}

int CheckNot(int s,int l){
return (s&l)||(s&(l>>1))||(s&(l<<1));
}

int CheckGood(int s){
int flg=0;
while(s){
	if(s&1 && flg)return 0;
	flg=s&1;
	s>>=1;
}
return 1;
}

void Get(){
for(int i=0;i<=ed;i++){cnt[i]=Cnt(i);rule[i]=CheckGood(i);}
}

int main(){
freopen("1087.in","r",stdin);
freopen("1087.out","w",stdout);
scanf("%lld %lld",&n,&K);
ed=(1<<n)-1;
Get();
for(int i=0;i<=ed;i++)if(rule[i])f[1][cnt[i]][i]=1;
for(int i=2;i<=n;i++){
	for(int j=0;j<=ed;j++){
		if(!rule[j])continue;
        for(int k=0;k<=ed;k++){
			if(!rule[k] || CheckNot(j,k))continue;
			for(int l=cnt[k];l+cnt[j]<=K;l++)f[i][l+cnt[j]][j]+=f[i-1][l][k];
        }
	}
}
for(int i=0;i<=ed;i++)ans+=f[n][K][i];
printf("%lld\n",ans);
return 0;
}

m<=2。。。

所以直接DP

m=1时

f[i][1][k]表示这一列前i个数选了k个子矩阵(中间的1没有用处)

那么转移就很像最大子段和:f[i][1][k]=max(f[i-1][1][k],f[j][1][k-1]+sum[i]-sum[j]);

前面表示不选择，后面表示选择j-i这一段所能带来的当前情况下的最大得分

m=2时复杂一些

f[i][j][k]表示第一列前i个数第二列前j个数选了k个子矩阵

那么转移分4种情况

1:f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);表示继承上一个状态的结果，不选择i或者j

2:f[i][j][k]=max(f[i][j][k],f[ix][j][k-1]+sum[i][1]-sum[ix][1]);表示选择ix-i这一段所能带来的当前情况下的最大得分

3:f[i][j][k]=max(f[i][j][k],f[i][jx][k-1]+sum[j][2]-sum[jx][2]);表示选择jx-j这一段所能带来的当前情况下的最大得分

4:if(i==j)f[i][j][k]=max(f[i][j][k],f[x][x][k-1]+sum[i][1]-sum[x][1]+sum[j][2]-sum[x][2]);表示同时选择两排所能带来的最大得分

最后输出f[n][n][k]就可以了，表示第一列和第二列都选完了，一共选择了k个子矩阵

难得写一次详细的题解……主要是因为我在狂补DP,DP渣到连前几年的普及组题目都写不出来……

去年NOIP D2T2居然不会写

这都坚定了我要补DP的决心……

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

int sum[105][5],f[105][105][15],a[105][5],n,m,K;

int main(){
freopen("1084.in","r",stdin);
freopen("1084.out","w",stdout);
scanf("%d %d %d",&n,&m,&K);
for(int i=1;i<=n;i++){
	for(int j=1;j<=m;j++){
		scanf("%d",&a[i][j]);
		sum[i][j]=sum[i-1][j]+a[i][j];
	}
}
memset(f,-127,sizeof(f));
if(m==1){
	for(int i=0;i<=n;i++)f[i][1][0]=0;
	for(int i=1;i<=n;i++){
		for(int k=1;k<=K;k++){
			f[i][1][k]=f[i-1][1][k];
			for(int j=0;j<i;j++){
				f[i][1][k]=max(f[i][1][k],f[j][1][k-1]+sum[i][1]-sum[j][1]);
			}
		}
	}
	printf("%d\n",f[n][1][K]);
}
else if(m==2){
	for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)f[i][j][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=K;k++){
				f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k]);
				for(int ix=0;ix<i;ix++)f[i][j][k]=max(f[i][j][k],f[ix][j][k-1]+sum[i][1]-sum[ix][1]);
				for(int jx=0;jx<j;jx++)f[i][j][k]=max(f[i][j][k],f[i][jx][k-1]+sum[j][2]-sum[jx][2]);
				if(i==j)for(int x=0;x<i;x++)f[i][j][k]=max(f[i][j][k],f[x][x][k-1]+sum[i][1]-sum[x][1]+sum[j][2]-sum[x][2]);
			}
		}
	}
	printf("%d\n",f[n][n][K]);
}
return 0;
}

又做了一道叫"tree"的题目。。

这题要开unsigned int!!!!

开int会WA!开int会WA!开int会WA!重要的事说三遍

#include<cstdio>
#include<algorithm>
using namespace std;

unsigned int n,q;

struct Node{
unsigned int v,sum,add,rev,mul,siz;
Node *ch[2],*fa;
Node(unsigned int val,Node *fat);
void Pushdown();
void Pushup();
}*root[100005],*Null;

Node::Node(unsigned int val,Node *fat){
v=sum=val;
mul=siz=1;
add=rev=0;
ch[0]=ch[1]=Null;
fa=fat;
}

void Node::Pushdown(){
if(rev){
	rev=0;
	if(ch[0]!=Null)ch[0]->rev^=1;
	if(ch[1]!=Null)ch[1]->rev^=1;
	swap(ch[0]->ch[0],ch[0]->ch[1]);
	swap(ch[1]->ch[0],ch[1]->ch[1]);
}
if(mul!=1){
	if(ch[0]!=Null){
		ch[0]->mul=(ch[0]->mul*mul)%51061;
		ch[0]->add=(ch[0]->add*mul)%51061;
		ch[0]->sum=(ch[0]->sum*mul)%51061;
		ch[0]->v=(ch[0]->v*mul)%51061;
	}
	if(ch[1]!=Null){
		ch[1]->mul=(ch[1]->mul*mul)%51061;
		ch[1]->add=(ch[1]->add*mul)%51061;
		ch[1]->sum=(ch[1]->sum*mul)%51061;
		ch[1]->v=(ch[1]->v*mul)%51061;
	}
	mul=1;
}
if(add){
	if(ch[0]!=Null){
		ch[0]->add=(ch[0]->add+add)%51061;
		ch[0]->sum=(ch[0]->sum+ch[0]->siz%51061*add)%51061;
		ch[0]->v=(ch[0]->v+add)%51061;
	}
	if(ch[1]!=Null){
		ch[1]->add=(ch[1]->add+add)%51061;
		ch[1]->sum=(ch[1]->sum+ch[1]->siz%51061*add)%51061;
		ch[1]->v=(ch[1]->v+add)%51061;
	}
	add=0;
}
}

void Node::Pushup(){
siz=1;
sum=v;
if(ch[0]!=Null){siz+=ch[0]->siz;sum=(sum+ch[0]->sum)%51061;}
if(ch[1]!=Null){siz+=ch[1]->siz;sum=(sum+ch[1]->sum)%51061;}
}

int Notroot(Node *p){
return (p->fa->ch[0]==p)||(p->fa->ch[1]==p);
}

void Prepare(Node *p){
if(Notroot(p))Prepare(p->fa);
p->Pushdown();
}

void Rotate(Node *x,int kind){
Node *y=x->fa,*z=y->fa;
y->ch[!kind]=x->ch[kind];
if(x->ch[kind]!=Null)x->ch[kind]->fa=y;
x->fa=z;
if(Notroot(y))z->ch[z->ch[1]==y]=x;
y->fa=x;
x->ch[kind]=y;
y->Pushup();
x->Pushup();
}

void Splay(Node *x){
Prepare(x);
while(Notroot(x)){
	Node *y=x->fa,*z=y->fa;
	if(!Notroot(y))Rotate(x,y->ch[0]==x);
	else {
		if(y->ch[0]==x && z->ch[0]==y){Rotate(y,1);Rotate(x,1);}
		else if(y->ch[0]==x && z->ch[1]==y){Rotate(x,1);Rotate(x,0);}
		else if(y->ch[1]==x && z->ch[0]==y){Rotate(x,0);Rotate(x,1);}
		else {Rotate(y,0);Rotate(x,0);}
	}
}
}

void Access(Node *x){
for(Node *y=Null;x!=Null;y=x,x=x->fa){Splay(x);x->ch[1]=y;x->Pushup();}
}

void Makeroot(Node *x){
Access(x);
Splay(x);
x->rev^=1;
swap(x->ch[0],x->ch[1]);
}

void Link(Node *x,Node *y){
Makeroot(x);
x->fa=y;
}

void Cut(Node *x,Node *y){
Makeroot(x);
Access(y);
Splay(y);
if(y->ch[0]==x){x->fa=Null;y->ch[0]=Null;}
}

Node *Find(Node *x){
Access(x);
Splay(x);
while(x->ch[0]!=Null)x=x->ch[0];
return x;
}

Node *ToLct(int x){
return root[x];
}

Node *GetNull(){
Node *p=new Node(0,Null);
p->ch[0]=p->ch[1]=p->fa=p;
p->siz=0;
return p;
}

void Add(int x,int y,int z){
Node *p=ToLct(x),*q=ToLct(y);
Makeroot(p);
Access(q);
Splay(q);
q->add=(q->add+z)%51061;
q->v=(q->v+z)%51061;
q->Pushup();
}

void Mul(int x,int y,int z){
Node *p=ToLct(x),*q=ToLct(y);
Makeroot(p);
Access(q);
Splay(q);
q->mul=(q->mul*z)%51061;
q->v=(q->v*z)%51061;
q->Pushup();
}

unsigned int Div(int x,int y){
Node *p=ToLct(x),*q=ToLct(y);
Makeroot(p);
Access(q);
Splay(q);
return q->sum;
}

int main(){
freopen("2631.in","r",stdin);
freopen("2631.out","w",stdout);
scanf("%d %d",&n,&q);
Null=GetNull();
for(int i=1;i<=n;i++)root[i]=new Node(1,Null);
for(int i=1;i<n;i++){
	int u,v;
    scanf("%d %d",&u,&v);
    Link(ToLct(u),ToLct(v));
}
for(int i=1;i<=q;i++){
    char s[3];
    scanf("%s",s);
    if(s[0]=='+'){
		int u,v,c;
		scanf("%d %d %d",&u,&v,&c);
		Add(u,v,c);
    }
    if(s[0]=='-'){
		int u1,v1,u2,v2;
		scanf("%d %d %d %d",&u1,&v1,&u2,&v2);
        Cut(ToLct(u1),ToLct(v1));
        Link(ToLct(u2),ToLct(v2));
    }
    if(s[0]=='*'){
		int u,v,c;
		scanf("%d %d %d",&u,&v,&c);
		Mul(u,v,c);
    }
    if(s[0]=='/'){
		int u,v;
		scanf("%d %d",&u,&v);
		printf("%d\n",Div(u,v));
    }
}
return 0;
}