[国家集训队]Tree

2024-03-16 23:38

文章标签 tree 国家集训队

本文主要是介绍[国家集训队]Tree，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Tree

题解

~~一道LCT板题。~~

看样子就像是一道LCT的板题，只需要将乘与加的懒标记分别传下去即可。

‘-’就是简单的树上加边与删边

‘/'就是查询和，update时更新即可。

不过需要注意一下在乘与加时懒标记与总数的变化。

$add_{son}= add_{son} \cdot mul_{fa}+ add_{fa}$

$mul_{son}= mul_{son} \cdot mul_{fa}$

$sum_{son}= sum_{son} \cdot mul_{fa}+ add_{fa} \cdot siz_{son}$

mul是乘的懒标记，add是加的懒标记，sum是当前和，siz是子树大小。

公式其实很好推的，关键是别直接乘与加，~~笔者就因为这个WA了~~

源码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<map>
using namespace std;
#define MAXN 100010
typedef long long LL;
#define int LL
typedef pair<LL,LL> pii;
#define gc() getchar()
const int INF=0x7f7f7f7f;
const int mo=51061;
template<typename _T>
inline void read(_T &x){_T f=1;x=0;char s=gc();while(s>'9'||s<'0'){if(s=='-')f=-1;s=gc();}while(s>='0'&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=gc();}x*=f;
}
class LCT{private:int val[MAXN],father[MAXN];int ch[MAXN][2];int lzyadd[MAXN],lzymul[MAXN];int siz[MAXN],sum[MAXN],rev[MAXN];int stak,sta[MAXN];void pushup(int x){siz[x]=(1+siz[ch[x][0]]+siz[ch[x][1]])%mo;sum[x]=(val[x]+sum[ch[x][0]]+sum[ch[x][1]])%mo;}void pushdown(int x){if(rev[x]){swap(ch[x][0],ch[x][1]);rev[x]=0;rev[ch[x][0]]^=1;rev[ch[x][1]]^=1;}if(lzymul[x]!=1||lzyadd[x]){(val[ch[x][0]]*=lzymul[x])%=mo;(val[ch[x][1]]*=lzymul[x])%=mo;(val[ch[x][0]]+=lzyadd[x])%=mo;(val[ch[x][1]]+=lzyadd[x])%=mo;(lzymul[ch[x][0]]*=lzymul[x])%=mo;(lzymul[ch[x][1]]*=lzymul[x])%=mo;(lzyadd[ch[x][0]]*=lzymul[x])%=mo;(lzyadd[ch[x][1]]*=lzymul[x])%=mo;(lzyadd[ch[x][0]]+=lzyadd[x])%=mo;(lzyadd[ch[x][1]]+=lzyadd[x])%=mo;(sum[ch[x][0]]*=lzymul[x])%=mo;(sum[ch[x][0]]+=siz[ch[x][0]]*lzyadd[x])%=mo;(sum[ch[x][1]]*=lzymul[x])%=mo;(sum[ch[x][1]]+=siz[ch[x][1]]*lzyadd[x])%=mo;lzyadd[x]=0;lzymul[x]=1;}}bool identify(int x){return ch[father[x]][1]==x;}bool isRoot(int x){return ch[father[x]][0]!=x&&ch[father[x]][1]!=x;}void connect(int x,int fa,int tag){father[x]=fa;ch[fa][tag]=x;}void rotate(int x){int y=father[x],z=father[y];pushdown(x);pushdown(y);int d1=identify(y),d2=identify(x);int B=ch[x][d2^1];father[x]=z;if(!isRoot(y))connect(x,z,d1);connect(B,y,d2);connect(y,x,d2^1);pushup(y);pushup(x);}void splay(int x){int y=x,top=0;sta[++top]=y;while(!isRoot(y))sta[++top]=(y=father[y]);while(top)pushdown(sta[top--]);for(int y=father[x];!isRoot(x);rotate(x),y=father[x])if(!isRoot(y))rotate(identify(x)==identify(y)?y:x);}public:void access(int x){for(int y=0;x;x=father[y=x])splay(x),ch[x][1]=y,pushup(x);}void makeroot(int x){access(x);splay(x);rev[x]^=1;//pushdown(x);}int findroot(int x){access(x);splay(x);pushdown(x);while(ch[x][0])pushdown(x=ch[x][0]);return x;}int split(int x,int y){makeroot(x);access(y);splay(y);return sum[y];}void linkTree(int x,int y){//printf("Link%d %d\n",x,y);makeroot(x);pushdown(x);if(findroot(y)!=x)father[x]=y;}void cutTree(int x,int y){//printf("Cut%d %d\n",x,y);makeroot(x);pushdown(x);if(findroot(y)!=x||father[x]!=y||ch[y][0]!=x||ch[x][1])return ;father[x]=ch[y][0]=0,pushup(x);}void modifyTree(int x,int y){if(val[x]==y)return ;splay(x);val[x]=y;}void addTree(int x,int y,int d){makeroot(x);access(y);splay(y);(val[y]+=d)%=mo;(sum[y]+=siz[y]*d)%=mo;(lzyadd[y]+=d)%=mo;pushdown(y);}void mulTree(int x,int y,int d){makeroot(x);access(y);splay(y);(val[y]*=d)%=mo;(sum[y]*=d)%=mo;(lzymul[y]*=d)%=mo;(lzyadd[y]*=d)%=mo;pushdown(y);}bool queryLink(int x,int y){makeroot(x);if(findroot(y)==x)return 1;return 0;}void build(int n){for(int i=1;i<=n;i++)val[i]=lzymul[i]=1;}
}Tree;
int n,q;
signed main(){ read(n);read(q);Tree.build(n);for(int i=1;i<n;i++){int u,v;read(u);read(v);Tree.linkTree(u,v);}for(int i=1;i<=q;i++){char opt[5];scanf("\n%s",opt);if(opt[0]=='+'){int u,v,c;read(u);read(v);read(c);Tree.addTree(u,v,c);}if(opt[0]=='-'){int u1,v1,u2,v2;read(u1);read(v1);read(u2);read(v2);Tree.cutTree(u1,v1);Tree.linkTree(u2,v2);}if(opt[0]=='*'){int u,v,c;read(u);read(v);read(c);Tree.mulTree(u,v,c);}if(opt[0]=='/'){int u,v;read(u);read(v);printf("%lld\n",Tree.split(u,v));}}return 0;
}