算法：树链剖分，可持久化线段树。
题目大意
给定 \(n\) 个结点的一棵树，\(m\) 次操作，操作有三种：
- 将 \(x\) 至 \(y\) 最短路径上的所有点的权值加上 \(delta\)。
- 对于 \(x\) 至 \(y\) 最短路径上的所有点 \(u\)，求 \(\sum\sum^{\operatorname{dis}(u,y)}_{i=1}i\)。
- 将这棵树回退到第 \(x\) 次 1 操作后的历史版本。
强制在线。
从部分分到正解
\(n,m \le 1000\)
对于 1、2 操作，暴力遍历 \(x\) 到 \(y\) 的路径，并且存下每次操作 1 后的版本，对于操作 3 直接修改整棵树。
时间复杂度 \(O(nm)\)。
树为一条链，\(n \le 30000,m \le 50000\)
无操作 3
我们考虑操作 2，将 \(x\) 到 \(y\) 的路径分成 \(x\) 到 \(lca\) 和 \(lca\) 到 \(y\) 两部分。
当点 \(P \in [x,lca]\) 时，这个点的贡献
\[\begin{split} res_P&=a_i\times\dfrac{(dep_i+dep_y-2\times dep_{lca})(dep_i+dep_y-2\times dep_{lca}+1)}{2}\\ &=a_i\times\dfrac{(dep_y+dep_y^2-4\times dep_{lca}\times dep_y+4\times dep_{lca}^2-2\times dep_{lca})+dep_i\times(1+2\times dep_y-4\times dep_{lca})+dep_i^2}{2}\\ &=a_i\times\dfrac{[dep_y\times(dep_y+1)-2\times dep_{lca}\times(2\times dep_y-2\times dep_{lca}+1)]+dep_i\times (1+2\times dep_y-4\times dep_{lca})+dep_i^2}{2} \end{split} \]当点 \(P\in [lca,y]\) 时，这个点的贡献
\[\begin{split} res_P&=a_i\times\dfrac{(dep_y-dep_i)(dep_y-dep_i+1)}{2}\\ &=a_i\times\dfrac{(dep_y+dep_y^2)+dep_i\times(-1-2\times dep_y)+dep_i^2}{2}\\ &=a_i\times\dfrac{dep_y\times(dep_y+1)+dep_i\times(-1-2\times dep_y)+dep_i^2}{2} \end{split} \]我们只需要维护权值总和、权值与深度之积的总和、权值与深度的平方之积的总和、深度的总和、深度的平方的总和，这恰好可以用线段树来维护。
时间复杂度 \(O(m\log n)\)。
有操作 3
有了刚才的分析，对于操作 3 只需要把线段树可持久化就行了。
时间复杂度 \(O(m\log n)\)。
\(n,m\le 10^5\)
将序列放在树上，通过树链剖分转化成上述问题。
时间复杂度 \(O(m \log^2n)\)。
代码
简直不要太码农······
/*
* Title: 10477 Problem R：【省选基础数据结构 树链剖分】【GDOI2016】疯狂动物城
* Source: AcCoders-省选基础5—数据结构
* URL: http://www.accoders.com/problem.php?cid=2716&pid=17
* Author: Steven_lzx
* Command: -std=c++23 -Wall -fno-ms-extensions
* Date: 2022.10.20
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN=1e5+10;
const ll MOD=20160501,INV2=10080251;
int n,m,cnt,now,ans,fa[MAXN],dep[MAXN],top[MAXN],son[MAXN],siz[MAXN],dfn[MAXN],rnk[MAXN],val[MAXN],root[MAXN],ls[MAXN*50],rs[MAXN*50],id[MAXN*50],idx,num;
ll sum[MAXN*50][5],lazy[MAXN*50];
vector<int> g[MAXN];
namespace SEGT
{
void pushup(int p,int l,int r)
{
int mid=(l+r)>>1;
sum[p][0]=(sum[ls[p]][0]+sum[rs[p]][0]+sum[rs[p]][2]*(mid-l+1)+1ll*(r-l+2)*(r-l+1)/2%MOD*lazy[p])%MOD;
sum[p][1]=(sum[ls[p]][1]+sum[rs[p]][1]+sum[ls[p]][2]*(r-mid)+1ll*(r-l+2)*(r-l+1)/2%MOD*lazy[p])%MOD;
sum[p][2]=(sum[ls[p]][2]+sum[rs[p]][2]+lazy[p]*(r-l+1))%MOD;
sum[p][3]=(sum[ls[p]][3]+sum[rs[p]][3]+sum[rs[p]][2]*(mid-l+1)*(mid-l+1)+sum[rs[p]][0]*2*(mid-l+1)+1ll*(r-l+1)*(r-l+2)*(2*r-2*l+3)/6%MOD*lazy[p])%MOD;
sum[p][4]=(sum[ls[p]][4]+sum[rs[p]][4]+sum[ls[p]][2]*(r-mid)%MOD*(r-mid)+sum[ls[p]][1]*2*(r-mid)+1ll*(r-l+1)*(r-l+2)*(2*r-2*l+3)/6%MOD*lazy[p])%MOD;
return;
}
void build(int &p,int l,int r)
{
int mid;
p=++num;
if(l==r)
{
fill(sum[p],sum[p]+5,val[rnk[l]]);
return;
}
mid=(l+r)>>1;
build(ls[p],l,mid);
build(rs[p],mid+1,r);
pushup(p,l,r);
return;
}
void update(int &p,int q,int l,int r,const int L,const int R,ll c)
{
int mid;
if(id[p]!=idx)
{
p=++num;
id[p]=idx;
ls[p]=ls[q];
rs[p]=rs[q];
lazy[p]=lazy[q];
memmove(sum[p],sum[q],sizeof(sum[q]));
}
if(L<=l&&r<=R)
{
lazy[p]=(lazy[p]+c)%MOD;
sum[p][0]=(sum[p][0]+1ll*(r-l+1)*(r-l+2)/2%MOD*c)%MOD;
sum[p][1]=(sum[p][1]+1ll*(r-l+1)*(r-l+2)/2%MOD*c)%MOD;
sum[p][2]=(sum[p][2]+c*(r-l+1))%MOD;
sum[p][3]=(sum[p][3]+1ll*(r-l+1)*(r-l+2)*(2*r-2*l+3)/6%MOD*c)%MOD;
sum[p][4]=(sum[p][4]+1ll*(r-l+1)*(r-l+2)*(2*r-2*l+3)/6%MOD*c)%MOD;
return;
}
mid=(l+r)>>1;
if(L<=mid)
update(ls[p],ls[q],l,mid,L,R,c);
if(R>mid)
update(rs[p],rs[q],mid+1,r,L,R,c);
pushup(p,l,r);
return;
}
ll query(int p,int l,int r,const int L,const int R,int k)
{
int mid;
if(!p)
return 0;
if(L==l&&r==R)
return sum[p][k];
mid=(l+r)>>1;
if(R<=mid)
return (query(ls[p],l,mid,L,R,k)+lazy[p]*(k==2?(R-L+1):(k<2?1ll*(R-L+1)*(R-L+2)/2%MOD:1ll*(R-L+1)*(R-L+2)*(2*R-2*L+3)/6%MOD)))%MOD;
if(L>mid)
return (query(rs[p],mid+1,r,L,R,k)+lazy[p]*(k==2?(R-L+1):(k<2?1ll*(R-L+1)*(R-L+2)/2%MOD:1ll*(R-L+1)*(R-L+2)*(2*R-2*L+3)/6%MOD)))%MOD;
if(!k)
return (query(ls[p],l,mid,L,mid,k)+query(rs[p],mid+1,r,mid+1,R,2)*(mid-L+1)+query(rs[p],mid+1,r,mid+1,R,k)+1ll*(R-L+1)*(R-L+2)/2%MOD*lazy[p])%MOD;
if(k==1)
return (query(ls[p],l,mid,L,mid,k)+query(ls[p],l,mid,L,mid,2)*(R-mid)+query(rs[p],mid+1,r,mid+1,R,k)+1ll*(R-L+1)*(R-L+2)/2%MOD*lazy[p])%MOD;
if(k==3)
return (query(ls[p],l,mid,L,mid,k)+query(rs[p],mid+1,r,mid+1,R,k)+query(rs[p],mid+1,r,mid+1,R,2)*(mid-L+1)%MOD*(mid-L+1)+query(rs[p],mid+1,r,mid+1,R,0)*2*(mid-L+1)+1ll*(R-L+1)*(R-L+2)*(2*R-2*L+3)/6%MOD*lazy[p])%MOD;
if(k==4)
return (query(ls[p],l,mid,L,mid,k)+query(rs[p],mid+1,r,mid+1,R,k)+query(ls[p],l,mid,L,mid,2)*(R-mid)%MOD*(R-mid)+query(ls[p],l,mid,L,mid,1)*2*(R-mid)+1ll*(R-L+1)*(R-L+2)*(2*R-2*L+3)/6%MOD*lazy[p])%MOD;
return (query(ls[p],l,mid,L,mid,k)+query(rs[p],mid+1,r,mid+1,R,k)+lazy[p]*(R-L+1))%MOD;
}
}
using namespace SEGT;
namespace GRAPH
{
void DFS1(int u,int f)
{
dep[u]=dep[f]+1;
fa[u]=f;
siz[u]=1;
for(int v:g[u])
{
if(v==f)
continue;
DFS1(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]])
son[u]=v;
}
return;
}
void DFS2(int u,int tp)
{
rnk[dfn[u]=++cnt]=u;
top[u]=tp;
if(son[u])
DFS2(son[u],tp);
for(int v:g[u])
if(v!=fa[u]&&v!=son[u])
DFS2(v,v);
return;
}
void change(int x,int y,int c)
{
++idx;
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])
swap(x,y);
update(root[idx],root[now],1,n,dfn[top[x]],dfn[x],c);
x=fa[top[x]];
}
if(dep[x]>dep[y])
swap(x,y);
update(root[idx],root[now],1,n,dfn[x],dfn[y],c);
now=idx;
return;
}
ll ask(int x,int y)
{
int siz1=0,siz3=0;
ll res1=0,res2=0,res3=0,res4=0,res5=0,sum2=0,sum1,sum3;
while(top[x]!=top[y])
{
if(dep[top[x]]>dep[top[y]])
{
sum1=query(root[now],1,n,dfn[top[x]],dfn[x],2);
sum3=query(root[now],1,n,dfn[top[x]],dfn[x],1);
res4=(res4+query(root[now],1,n,dfn[top[x]],dfn[x],4)+sum1*siz1%MOD*siz1+sum3*2*siz1)%MOD;
res1=(res1+sum3+sum1*siz1)%MOD;
res3=(res3+sum1)%MOD;
siz1+=dfn[x]-dfn[top[x]]+1;
siz3+=dfn[x]-dfn[top[x]]+1;
x=fa[top[x]];
}
else
{
sum1=query(root[now],1,n,dfn[top[y]],dfn[y],2);
res5=((res5+query(root[now],1,n,dfn[top[y]],dfn[y],3)+sum2*(dfn[y]-dfn[top[y]]+1)%MOD*(dfn[y]-dfn[top[y]]+1)+res2*2*(dfn[y]-dfn[top[y]]+1)))%MOD;
res2=(res2+(dfn[y]-dfn[top[y]]+1)*sum2+query(root[now],1,n,dfn[top[y]],dfn[y],0))%MOD;
res3=(res3+sum1)%MOD;
sum2=(sum2+sum1)%MOD;
siz3+=dfn[y]-dfn[top[y]]+1;
y=fa[top[y]];
}
}
if(dep[x]<dep[y])
{
sum1=query(root[now],1,n,dfn[x],dfn[y],2);
res5=((res5+query(root[now],1,n,dfn[x],dfn[y],3)+sum2*(dfn[y]-dfn[x]+1)%MOD*(dfn[y]-dfn[x]+1)+res2*2*(dfn[y]-dfn[x]+1)))%MOD;
res2=(res2+(dfn[y]-dfn[x]+1)*sum2+query(root[now],1,n,dfn[x],dfn[y],0))%MOD;
res3=(res3+sum1)%MOD;
sum2=(sum2+sum1)%MOD;
siz3+=dfn[y]-dfn[x]+1;
}
else
{
sum1=query(root[now],1,n,dfn[y],dfn[x],2);
sum3=query(root[now],1,n,dfn[y],dfn[x],1);
res4=(res4+query(root[now],1,n,dfn[y],dfn[x],4)+sum1*siz1%MOD*siz1+sum3*2*siz1)%MOD;
res1=(res1+sum3+sum1*siz1)%MOD;
res3=(res3+sum1)%MOD;
siz1+=dfn[x]-dfn[y]+1;
siz3+=dfn[x]-dfn[y]+1;
}
res4=(res4+res5+sum2*siz1%MOD*siz1+res2*2*siz1)%MOD;
res1=(res1+sum2*siz1+res2)%MOD;
return ((1ll*siz3*(siz3+1)%MOD*res3-(2*siz3+1)*res1+res4)%MOD*INV2%MOD+MOD)%MOD;
}
}
using namespace GRAPH;
int main()
{
int x,y,op,delta;
scanf("%d%d",&n,&m);
for(int i=1;i<n;i++)
{
scanf("%d%d",&x,&y);
g[x].push_back(y);
g[y].push_back(x);
}
for(int i=1;i<=n;i++)
scanf("%d",val+i);
DFS1(1,0);
DFS2(1,1);
build(root[0],1,n);
while(m--)
{
scanf("%d",&op);
if(op==1)
{
scanf("%d%d%d",&x,&y,&delta);
change(x^ans,y^ans,delta);
}
else if(op==2)
{
scanf("%d%d",&x,&y);
printf("%d\n",ans=ask(x^ans,y^ans));
}
else
{
scanf("%d",&x);
now=x^ans;
}
}
return 0;
}