一个巨烦的时间轴分块做法，有点类似于 P2137 Gty的妹子树
先考虑静态的情况。看上去就一脸线段树合并对吧？一次修改的操作对一个点 \(x\) 贡献可以写成 \(k·dep_x+b\) 的形式，开两棵线段树合并维护一次项和零次项系数即可。
由于静态问题可做，因此考虑时间轴分块。设阈值 \(B\)，每 \(B\) 次操作进行一次重构，每次询问时，上一次重构前的答案可以用线段树合并的信息得到，对于上一次重构后的修改操作，我们将路径上的点分为两类，一是在重构的时候就存在于树中的，我们称之为白点，二是在重构后新加的，我们称之为黑点。每次加入一条路径时，我们先找到这条路径两个端点的 LCA，具体方法是，如果两个点之一是黑点且两个点不同就暴力跳那个深度较大的黑点，否则此时两个点都是白点，我们就直接调用上次重构的结果。查询的时候考虑所有新加进来的路径，如果 LCA 在待查询点的子树内，那么这条路径对询问的贡献是 \(k·\text{路径长度}\)，否则这条路径对询问的贡献是 \(k·(dep_u+dep_v-2dep_x+1)\)。
毛估估一下复杂度是 \(\dfrac{nq}{B}\log n+(n+q)B\)，由于前面的 \(\log\) 常数实在是太大了，因此 \(B\) 大概要开到 \(2000\) 的样子才能过。
const int MAXN=2e5;
const int MAXV=1e9;
const int LOG_N=17;
const int BLK=2000;
const int MAXP=MAXN<<7;
int n,qu,hd[MAXN+5],to[MAXN*2+5],nxt[MAXN*2+5],ec=0,ncnt;
struct qry{int opt,u,v,c,k,lc;}q[MAXN+5];
int dfn[MAXN+5],edt[MAXN+5],fa[MAXN+5][LOG_N+2],dep[MAXN+5],lst,lst_ncnt,tim;
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
struct segtree{
struct node{int ch[2];ll sum;}s[MAXP+5];
int rt[MAXN+5],cc=0;
void init(){
memset(rt,0,sizeof(rt));
for(int i=1;i<=cc;i++)s[i].ch[0]=s[i].ch[1]=s[i].sum=0;cc=0;
}
void insert(int &k,int l,int r,int p,ll v){
if(!k)k=++cc,assert(cc<=MAXP);s[k].sum+=v;if(l==r)return;
int mid=l+r>>1;
if(p<=mid)insert(s[k].ch[0],l,mid,p,v);
else insert(s[k].ch[1],mid+1,r,p,v);
}
int merge(int x,int y,int l,int r){
if(!x||!y)return x+y;
int z=++cc;assert(cc<=MAXP);s[z].sum=s[x].sum+s[y].sum;
if(l==r)return z;int mid=l+r>>1;
s[z].ch[0]=merge(s[x].ch[0],s[y].ch[0],l,mid);
s[z].ch[1]=merge(s[x].ch[1],s[y].ch[1],mid+1,r);
return z;
}
ll query(int k,int l,int r,int ql,int qr){
if(!k)return 0;if(ql<=l&&r<=qr)return s[k].sum;
int mid=l+r>>1;
if(qr<=mid)return query(s[k].ch[0],l,mid,ql,qr);
else if(ql>mid)return query(s[k].ch[1],mid+1,r,ql,qr);
else return query(s[k].ch[0],l,mid,ql,mid)+query(s[k].ch[1],mid+1,r,mid+1,qr);
}
}T1,T0;
vector<pair<int,ll> >V0[MAXN+5],V1[MAXN+5];
void dfs1(int x,int f){
fa[x][0]=f;dfn[x]=++tim;
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];if(y==f)continue;
dep[y]=dep[x]+1;dfs1(y,x);
}edt[x]=tim;
}
void dfs2(int x,int f){
for(pair<int,ll> p:V1[x])T1.insert(T1.rt[x],1,MAXV,p.fi,p.se);
for(pair<int,ll> p:V0[x])T0.insert(T0.rt[x],1,MAXV,p.fi,p.se);
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];if(y==f)continue;dfs2(y,x);
T0.rt[x]=T0.merge(T0.rt[x],T0.rt[y],1,MAXV);
T1.rt[x]=T1.merge(T1.rt[x],T1.rt[y],1,MAXV);
}
// printf("?! %d %lld %lld\n",x,T0.s[T0.rt[x]].sum,T1.s[T1.rt[x]].sum);
}
int getlca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=LOG_N;~i;i--)if(dep[x]-(1<<i)>=dep[y])x=fa[x][i];
if(x==y)return x;
for(int i=LOG_N;~i;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
int f0[MAXN+5],anc[BLK+5][BLK+5];
int find(int x){return (!f0[x])?x:f0[x]=find(f0[x]);}
bool checkin(int u,int x){
if(u<=lst_ncnt){x=find(x);return dfn[u]<=dfn[x]&&dfn[x]<=edt[u];}
else{
if(x<=lst_ncnt)return 0;
else return anc[x-lst_ncnt][u-lst_ncnt];
}
}
void rebuild(int TIM){
// printf("rebuild %d\n",TIM);
tim=0;memset(f0,0,sizeof(f0));memset(anc,0,sizeof(anc));
T1.init();T0.init();
for(int i=lst+1;i<=TIM;i++)if(q[i].opt==1)adde(q[i].u,q[i].v),adde(q[i].v,q[i].u);
dfs1(1,0);
for(int i=1;i<=LOG_N;i++)for(int j=1;j<=ncnt;j++)
fa[j][i]=fa[fa[j][i-1]][i-1];
for(int i=lst+1;i<=TIM;i++)if(q[i].opt==2){
V0[q[i].u].pb(mp(q[i].c,1ll*q[i].k*(dep[q[i].u]+1)));
V0[q[i].v].pb(mp(q[i].c,1ll*q[i].k*(dep[q[i].v]+1)));
V0[q[i].lc].pb(mp(q[i].c,-1ll*q[i].k*(dep[q[i].u]+1+dep[q[i].v]+1)));
V1[q[i].u].pb(mp(q[i].c,-q[i].k));
V1[q[i].v].pb(mp(q[i].c,-q[i].k));
V1[q[i].lc].pb(mp(q[i].c,2*q[i].k));
V0[q[i].lc].pb(mp(q[i].c,1ll*q[i].k*(dep[q[i].u]+dep[q[i].v]-2*dep[q[i].lc]+1)));
}dfs2(1,0);
lst=TIM;lst_ncnt=ncnt;
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d",&n,&qu);ncnt=n;
for(int i=1,u,v;i<n;i++)scanf("%d%d",&u,&v),adde(u,v),adde(v,u);
rebuild(0);int lstans=0;
for(int i=1;i<=qu;i++){
scanf("%d",&q[i].opt);
if(q[i].opt==1){
int U;scanf("%d",&U);U^=lstans;
q[i].u=U;q[i].v=++ncnt;
dep[ncnt]=dep[U]+1;fa[ncnt][0]=U;f0[ncnt]=U;
for(int j=ncnt;j>lst_ncnt;j=fa[j][0])anc[ncnt-lst_ncnt][j-lst_ncnt]=1;
}else if(q[i].opt==2){
int U,V,C,K;scanf("%d%d%d%d",&U,&V,&C,&K);
U^=lstans,V^=lstans,C^=lstans,K^=lstans;
q[i].u=U;q[i].v=V;q[i].c=C;q[i].k=K;
int tu=U,tv=V;if(dep[tu]<dep[tv])swap(tu,tv);
while(dep[tu]>dep[tv]&&tu>lst_ncnt)tu=fa[tu][0];
while(tu!=tv&&(tu>lst_ncnt||tv>lst_ncnt)){
if(tu>lst_ncnt)tu=fa[tu][0];
if(tv>lst_ncnt)tv=fa[tv][0];
}q[i].lc=(tu==tv)?tu:getlca(tu,tv);
}else{
int U,C;scanf("%d%d",&U,&C);U^=lstans,C^=lstans;
q[i].u=U,q[i].c=C;
ll res=(U<=ncnt)?(T0.query(T0.rt[U],1,MAXV,1,C)+
1ll*dep[U]*T1.query(T1.rt[U],1,MAXV,1,C)):0;
for(int j=lst+1;j<=i;j++)if(q[j].opt==2&&q[j].c<=C){
if(checkin(U,q[j].lc))res+=1ll*q[j].k*(dep[q[j].u]+dep[q[j].v]-dep[q[j].lc]*2+1);
else{
int ss=0;
if(checkin(U,q[j].u))ss+=dep[q[j].u]-dep[U]+1;
if(checkin(U,q[j].v))ss+=dep[q[j].v]-dep[U]+1;
res+=1ll*ss*q[j].k;
}
}printf("%lld\n",res);lstans=res;
if(lstans<0)lstans+=2147483648u;
}
if(i%BLK==0)rebuild(i);
}
return 0;
}