[国家集训队] Tree II
一道·真·板子·题
就是练习LCT懒标记的题目
除了翻转标记以外还要维护乘法标记和加法标记
注意加法标记和乘法标记的维护！！！
加法标记
因为splay的区间大小不是固定的，所以我们要维护size，并且子树的sum要加上size乘上标记
其他的就只用直接加上即可
void pushadd(ll x,ll c){
t[x].sum=(t[x].sum+t[x].sz*c%P)%P;
t[x].val=(t[x].val+c)%P;
t[x].add=(t[x].add+c)%P;
}
乘法标记
由于乘法的优先级要大于加法
所以我们的加法标记也要乘上乘法标记值
void pushmul(ll x,ll c){
t[x].sum=t[x].sum*c%P;
t[x].val=t[x].val*c%P;
t[x].mul=t[x].mul*c%P;
t[x].add=t[x].add*c%P;
}
注意：int过不了！！！
CODE
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+2,P=51061;
ll n,q,s[N];
struct node{ll ch[2],p,sum,tag,sz,val,mul,add;}t[N];
void pushtag(ll x){
swap(t[x].ch[0],t[x].ch[1]);
t[x].tag^=1;
}
void pushmul(ll x,ll c){
t[x].sum=t[x].sum*c%P;
t[x].val=t[x].val*c%P;
t[x].mul=t[x].mul*c%P;
t[x].add=t[x].add*c%P;
}
void pushadd(ll x,ll c){
t[x].sum=(t[x].sum+t[x].sz*c%P)%P;
t[x].val=(t[x].val+c)%P;
t[x].add=(t[x].add+c)%P;
}
void pushup(ll x){
t[x].sum=(t[t[x].ch[0]].sum+t[x].val+t[t[x].ch[1]].sum)%P;
t[x].sz=t[t[x].ch[0]].sz+t[t[x].ch[1]].sz+1;
}
void pushdown(ll x){
if(t[x].mul!=1){
pushmul(t[x].ch[0],t[x].mul);
pushmul(t[x].ch[1],t[x].mul);
t[x].mul=1;
}
if(t[x].add){
pushadd(t[x].ch[0],t[x].add);
pushadd(t[x].ch[1],t[x].add);
t[x].add=0;
}
if(t[x].tag){
pushtag(t[x].ch[0]);
pushtag(t[x].ch[1]);
t[x].tag=0;
}
}
bool isrt(ll x){//判断节点x是否是当前实树的根
return t[t[x].p].ch[0]!=x&&t[t[x].p].ch[1]!=x;
}
void rotate(ll x){//x上旋
ll y=t[x].p,z=t[y].p;
ll k=(t[y].ch[1]==x);//x原来的位置
if(!isrt(y)) t[z].ch[(t[z].ch[1]==y)]=x;//x代替y位置
t[x].p=z;
t[y].ch[k]=t[x].ch[k^1];
t[t[x].ch[k^1]].p=y;
t[x].ch[k^1]=y;
t[y].p=x;
pushup(y);
pushup(x);
}
void splay(ll x){//x上旋到根
ll top=0,r=x;
s[++top]=r;
while(!isrt(r)){
s[++top]=r=t[r].p;
}
while(top) pushdown(s[top--]);
while(!isrt(x)){
ll y=t[x].p,z=t[y].p;
if(!isrt(y)){//y不为目标位置
if((t[y].ch[1]==x)^(t[z].ch[1]==y)) rotate(x);//不在同一直线上
else rotate(y);//在同一直线上
}
rotate(x);
}
}
void access(ll x){// 把根节点到x的路径上的边全部变为实边，同时将x变成splay的根节点
ll z=x;
for(ll y=0;x;y=x,x=t[x].p){
splay(x);
t[x].ch[1]=y;//右子树
pushup(x);
}
splay(z);
}
void makert(ll x){// 将x变成原树的根节点
access(x);//打通一条从根到x的路径 然后将x旋到根
//首先 打通一条从根到x的路径 后 x 是 d最大的点
//因此 此时，x必然是Splay中中序遍历最后得到的点
pushtag(x);//翻转Splay ， x成为 中序遍历 第一个点->即原树根节点
}
ll findrt(ll x) {// 找到x所在原树的根节点, 再将原树的根节点旋转到splay的根节点
access(x);//x与原树根在同一splay内
//由于每个Splay中维护的节点按中序遍历得到的顺序在原树中深度依次增加1
//所以根节点必然是Splay中序遍历顺序为1的节点
while(t[x].ch[0]){
pushdown(x);
x=t[x].ch[0];
}
//路径深度最小
splay(x);
return x;
}
void split(ll x,ll y){ // 给x和y之间的路径建1个splay，其根节点是y
makert(x);
access(y);
}
void link(ll x,ll y){//如果x和y不连通,加1条x和y之间的边
makert(x);// 将x作为它所在树的根
if(findrt(y)!=x){//不连通
t[x].p=y;//更新x的父亲为y
}
}
bool back(ll x,ll y){//y是否是x的后继
return t[x].ch[1]==y&&!t[y].ch[0];
}
void cut(ll x,ll y){// 如果x和y之间存在边，则删除该边
split(x,y);//只剩下x->y,x是y的做儿子
if(t[x].ch[1]||t[x].p!=y||t[y].ch[1])return ;
t[t[y].ch[0]].p=0;
t[y].ch[0]=0;
}
int main(){
scanf("%lld%lld",&n,&q);
for(ll i=1;i<=n;i++){
t[i].val=t[i].sz=t[i].mul=1;
}
for(ll i=1,x,y;i<n;i++){
scanf("%lld%lld",&x,&y);
link(x,y);
}
for(ll i=1;i<=q;i++){
char op[10];
ll x,y,k;
scanf("%s",op);
if(op[0]=='+'){
scanf("%lld%lld%lld",&x,&y,&k);
split(x,y),pushadd(y,k);
}else if(op[0]=='-'){
scanf("%lld%lld",&x,&y);
cut(x,y);
scanf("%lld%lld",&x,&y);
link(x,y);
}else if(op[0]=='*'){
scanf("%lld%lld%lld",&x,&y,&k);
split(x,y),pushmul(y,k);
}else{
scanf("%lld%lld",&x,&y);
split(x,y);
printf("%lld\n",t[y].sum);
}
}
return 0;
}
完结撒花❀
★,°:.☆(￣▽￣)/$:.°★ 。