LuoguP1501 Tree Ⅱ
颓数据结构题真好
题意
你需要维护一颗树，支持动态更改边，路径乘法，路径加法，询问路径节点权值和。初始节点权值都为1，保证每时每刻这都是一棵树，让你对于每个询问输出答案。
题解
数据结构题真是酸爽啊一道裸的(LCT)题目，实际上并不难，只是维护这个路径加和路径乘的细节需要的有点多。。打挂了两遍，续掉了半个小时（舒服）。实际上代码实现难度并不难，就是一些(LCT)的基础操作，细心一点就行了。实际上感觉自己三遍调出来还是挺腻害的。。（逃
Code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
bool Finish_read;
template<class T>inline void read(T &x){Finish_read=0;x=0;int f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-1;if(ch==EOF)return;ch=getchar();}while(isdigit(ch))x=x*10+ch-'0',ch=getchar();x*=f;Finish_read=1;}
template<class T>inline void print(T x){if(x/10!=0)print(x/10);putchar(x%10+'0');}
template<class T>inline void writeln(T x){if(x<0)putchar('-');x=abs(x);print(x);putchar('
');}
template<class T>inline void write(T x){if(x<0)putchar('-');x=abs(x);print(x);}
/*================Header Template==============*/
const int maxn=1e5+500;
const int Md=51061;
int n,q;
/*==================Define Area================*/
namespace LCT {
struct node {
int ch[2],fa,rev,sz;
ll sum,addtag,multag,val;
}t[maxn];
#define ls(o) t[o].ch[0]
#define rs(o) t[o].ch[1]
#define pa(o) t[o].fa
void init() {for(int i=1;i<=n;i++) t[i].multag=1,t[i].val=1;}
int Which(int o) {return t[pa(o)].ch[1]==o;}
int IsRoot(int o) {return t[pa(o)].ch[0]!=o&&t[pa(o)].ch[1]!=o;}
void RevNode(int o) {t[o].rev^=1;swap(ls(o),rs(o));}
void Update(int o) {
t[o].sum=t[ls(o)].sum+t[rs(o)].sum+t[o].val;t[o].sum%=Md;
t[o].sz=1;
if(ls(o)) t[o].sz+=t[ls(o)].sz;
if(rs(o)) t[o].sz+=t[rs(o)].sz;
}
void Pushdown(int o) {
if(!o) return ;
if(t[o].rev) {
if(ls(o)) RevNode(ls(o));
if(rs(o)) RevNode(rs(o));
t[o].rev=0;
}
if(t[o].multag!=1) {
t[ls(o)].multag*=t[o].multag;t[ls(o)].multag%=Md;
t[rs(o)].multag*=t[o].multag;t[rs(o)].multag%=Md;
t[ls(o)].addtag*=t[o].multag;t[ls(o)].addtag%=Md;
t[rs(o)].addtag*=t[o].multag;t[rs(o)].addtag%=Md;
t[ls(o)].sum*=t[o].multag;t[ls(o)].sum%=Md;
t[rs(o)].sum*=t[o].multag;t[rs(o)].sum%=Md;
t[ls(o)].val*=t[o].multag;t[ls(o)].val%=Md;
t[rs(o)].val*=t[o].multag;t[rs(o)].val%=Md;
t[o].multag=1;
}
if(t[o].addtag) {
t[ls(o)].addtag+=t[o].addtag;t[ls(o)].addtag%=Md;
t[rs(o)].addtag+=t[o].addtag;t[rs(o)].addtag%=Md;
t[ls(o)].sum+=t[o].addtag*t[ls(o)].sz;t[ls(o)].sum%=Md;
t[rs(o)].sum+=t[o].addtag*t[rs(o)].sz;t[rs(o)].sum%=Md;
t[ls(o)].val+=t[o].addtag;t[ls(o)].val%=Md;
t[rs(o)].val+=t[o].addtag;t[rs(o)].val%=Md;
t[o].addtag=0;
}
}
void Rotate(int o) {
int f=t[o].fa,ff=t[f].fa,c=Which(o);
if(!IsRoot(f)) t[ff].ch[Which(f)]=o;t[o].fa=ff;
t[f].ch[c]=t[o].ch[c^1];t[t[f].ch[c]].fa=f;
t[o].ch[c^1]=f;t[f].fa=o;
Update(f);Update(o);
}
void TreePushdown(int o) {if(!IsRoot(o)) TreePushdown(pa(o));Pushdown(o);}
void Splay(int o) {
TreePushdown(o);
for(;!IsRoot(o);Rotate(o)) {
if(!IsRoot(pa(o))) Rotate(Which(pa(o))==Which(o)?pa(o):o);
}
}
void Access(int o) {for(int y=0;o;y=o,o=pa(o)) Splay(o),rs(o)=y,Update(o);}
void MakeRoot(int o) {Access(o);Splay(o);RevNode(o);}
void Link(int x,int y) {MakeRoot(x);t[x].fa=y;}
void Cut(int x,int y) {MakeRoot(x);Access(y);Splay(y);t[x].fa=t[y].ch[0]=0;Update(y);}
void Split(int x,int y) {MakeRoot(x);Access(y);Splay(y);}
void Add(int x,int y,ll v) {Split(x,y);t[y].sum+=v*t[y].sz;t[y].val+=v;t[y].sum%=Md;t[y].val%=Md;t[y].addtag+=v;t[y].addtag%=Md;}
void Mul(int x,int y,ll v) {Split(x,y);t[y].multag*=v;t[y].multag%=Md;t[y].addtag*=v;t[y].addtag%=Md;t[y].val*=v;t[y].val%=Md;}
ll Query(int x,int y) {
Split(x,y);
return t[y].sum;
}
}
using namespace LCT;
int main() {
read(n);read(q);
init();
for(int i=1,u,v;i<n;i++) {
read(u);read(v);
Link(u,v);
}
while(q--) {
char opt[2];
scanf("%s",opt);
if(opt[0]=='+') {
int u,v;
ll c;
read(u);read(v);read(c);
Add(u,v,c);
}
if(opt[0]=='-') {
int u1,v1,u2,v2;
read(u1);read(v1);read(u2);read(v2);
Cut(u1,v1);Link(u2,v2);
}
if(opt[0]=='*') {
int u,v;
ll c;
read(u);read(v);read(c);
Mul(u,v,c);
}
if(opt[0]=='/') {
int u,v;
read(u);read(v);
printf("%lld
",Query(u,v));
}
}
return 0;
}