大致题意： 有一棵初始边权全为(1)的树，四种操作：将两点间路径边权都加上一个数，删一条边、加一条新边，将两点间路径边权都加上一个数，询问两点间路径权值和。
序列版
这道题有一个序列版：【洛谷3373】【模板】线段树 2。
看题目就知道是一道线段树板子题。
这种题目移到树上路径中，且要删边加边，是(LCT)无疑了。
(LCT)维护懒惰标记
可以说，这道题就是上面那题的翻版。
同样维护两个标记：乘法标记和加法标记，加上原有的翻转标记，共三个标记。
具体细节其实可以详见上面提到的那道线段树板子题，这里就不多说了。
主要是要注意标记下传与更新的优先级问题，应该是乘法先，加法后，至于翻转标记在前在后都无所谓。
代码
#include<bits/stdc++.h>
#define N 100000
#define MOD 51061
#define swap(x,y) (x^=y^=x^=y)
#define Inc(x,y) ((x+=(y))>=MOD&&(x-=MOD))
using namespace std;
int n,ee,lnk[N+5];
class Class_FIO
{
private:
#define Fsize 100000
#define tc() (A==B&&(B=(A=Fin)+fread(Fin,1,Fsize,stdin),A==B)?EOF:*A++)
#define pc(ch) (FoutSize<Fsize?Fout[FoutSize++]=ch:(fwrite(Fout,1,Fsize,stdout),Fout[(FoutSize=0)++]=ch))
int Top,FoutSize;char ch,*A,*B,Fin[Fsize],Fout[Fsize],Stack[Fsize];
public:
Class_FIO() {A=B=Fin;}
inline void read(int &x) {x=0;while(!isdigit(ch=tc()));while(x=(x<<3)+(x<<1)+(ch&15),isdigit(ch=tc()));}
inline void readc(char &x) {while(isspace(x=tc()));}
inline void writeln(int x) {while(Stack[++Top]=x%10+48,x/=10);while(Top) pc(Stack[Top--]);pc('
');}
inline void clear() {fwrite(Fout,1,FoutSize,stdout),FoutSize=0;}
}F;
class Class_LCT//LCT板子
{
private:
#define LCT_SIZE N
#define PushUp(x) (node[x].Size=node[node[x].Son[0]].Size+node[node[x].Son[1]].Size+1,node[x].Sum=(node[x].Val+node[node[x].Son[0]].Sum+node[node[x].Son[1]].Sum)%MOD)
#define MulVal(x,v) (node[x].Sum=1LL*node[x].Sum*v%MOD,node[x].Val=1LL*node[x].Val*v%MOD,node[x].flag1=1LL*node[x].flag1*v%MOD,node[x].flag2=1LL*node[x].flag2*v%MOD)
#define AddVal(x,v) (Inc(node[x].Sum,1LL*node[x].Size*v%MOD),Inc(node[x].Val,v),Inc(node[x].flag2,v))
#define Rever(x) (swap(node[x].Son[0],node[x].Son[1]),node[x].Rev^=1)
#define PushDown(x)
(
node[x].flag1^1&&(MulVal(node[x].Son[0],node[x].flag1),MulVal(node[x].Son[1],node[x].flag1),node[x].flag1=1),
node[x].flag2&&(AddVal(node[x].Son[0],node[x].flag2),AddVal(node[x].Son[1],node[x].flag2),node[x].flag2=0),
node[x].Rev&&(Rever(node[x].Son[0]),Rever(node[x].Son[1]),node[x].Rev=0)
)
#define Which(x) (node[node[x].Father].Son[1]==x)
#define Connect(x,y,d) (node[node[x].Father=y].Son[d]=x)
#define IsRoot(x) (node[node[x].Father].Son[0]^x&&node[node[x].Father].Son[1]^x)
#define MakeRoot(x) (Access(x),Splay(x),Rever(x))
#define Split(x,y) (MakeRoot(x),Access(y),Splay(y))
int Stack[LCT_SIZE+5];
struct Tree
{
int Val,Sum,Size,flag1,flag2,Rev,Father,Son[2];
}node[LCT_SIZE+5];
inline void Rotate(int x)
{
register int fa=node[x].Father,pa=node[fa].Father,d=Which(x);
!IsRoot(fa)&&(node[pa].Son[Which(fa)]=x),node[x].Father=pa,Connect(node[x].Son[d^1],fa,d),Connect(fa,x,d^1),PushUp(fa),PushUp(x);
}
inline void Splay(int x)
{
register int fa=x,Top=0;
while(Stack[++Top]=fa,!IsRoot(fa)) fa=node[fa].Father;
while(Top) PushDown(Stack[Top]),--Top;
while(!IsRoot(x)) fa=node[x].Father,!IsRoot(fa)&&(Rotate(Which(x)^Which(fa)?x:fa),0),Rotate(x);
}
inline void Access(int x) {for(register int son=0;x;x=node[son=x].Father) Splay(x),node[x].Son[1]=son,PushUp(x);}
inline int FindRoot(int x) {Access(x),Splay(x);while(node[x].Son[0]) PushDown(x),x=node[x].Son[0];return Splay(x),x;}
public:
inline void Init(int len) {for(register int i=1;i<=len;++i) node[i].Val=node[i].flag1=1;}
inline void Link(int x,int y) {MakeRoot(x),FindRoot(y)^x&&(node[x].Father=y);}
inline void Cut(int x,int y) {MakeRoot(x),!(FindRoot(y)^x)&&!(node[y].Father^x)&&!node[y].Son[0]&&(node[y].Father=node[x].Son[1]=0,PushUp(x));}
inline void Mul(int x,int y,int v) {Split(x,y),MulVal(y,v);}
inline void Add(int x,int y,int v) {Split(x,y),AddVal(y,v);}
inline int Query(int x,int y) {return Split(x,y),node[y].Sum;}
}LCT;
int main()
{
register int query_tot,i,x,y,z;register char op;
for(F.read(n),F.read(query_tot),LCT.Init(n),i=1;i<n;++i) F.read(x),F.read(y),LCT.Link(x,y);
while(query_tot--)
{
F.readc(op),F.read(x),F.read(y);
switch(op)
{
case '*':F.read(z),LCT.Mul(x,y,z);break;
case '+':F.read(z),LCT.Add(x,y,z);break;
case '-':LCT.Cut(x,y),F.read(x),F.read(y),LCT.Link(x,y);break;
case '/':F.writeln(LCT.Query(x,y));break;
}
}
return F.clear(),0;
}