[国家集训队] Tree II 题解报告

[国家集训队] Tree II

加法标记

因为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，其根节点是ymakert(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;
} 

完结撒花❀
★,°:.☆(￣▽￣)/$:.°★ 。