分析
考虑把每个询问拆成 $\sum_{i=1}^r\operatorname{dis}(p_i,u)-\sum_{i=1}^{l-1}\operatorname{dis}(p_i,u)$。
我们考虑怎么求 $\sum_{i=1}^t\operatorname{dis}(p_i,u)$，这个东西可以拆成 $t\times dep_u+\sum_{i=1}^t dep_{p_i}-2\sum_{i=1}^t dep_{\operatorname{LCA}(p_i,u)}$。
前两个很好维护，我们只要考虑求 $\sum_{i=1}^t dep_{\operatorname{LCA}(p_i,u)}$。
这是一个经典问题。我们把每个 $p_{1..t}$ 到根的路径全部加上 $1$，然后查询 $u$ 到根的路径的和即可。
这样子就可以直接树链剖分+可持久化线段树预处理，修改时可以发现只会修改第 $x$ 个版本，直接从上个版本重新修改一次即可。
因为有区间加，所以需要标记永久化。
然而空间可能开不下，有两个优化：第一个是在跳重链修改时不新建本次跳重链过程中新建的点，另一个是在修改达到一定次数时直接清空可持久化线段树然后重建。这样子就可以卡过去了。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=200000+10;
int n,Q,p[N]; ll sum[N],pre[N];
struct edge { int v,w,nxt; } e[N<<1];
int head[N];
void addEdge(int u,int v,int w) {
static int cnt=0;
e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
}
int fa[N],sz[N],hson[N],top[N],fw[N]; ll dep[N];
int dfn[N],pos[N],tim=0;
void dfs1(int u,int f) {
fa[u]=f,sz[u]=1;
for (int i=head[u];i;i=e[i].nxt) {
int v=e[i].v,w=e[i].w; if (v==f) continue;
fw[v]=w,dep[v]=dep[u]+w,dfs1(v,u),sz[u]+=sz[v];
if (sz[v]>sz[hson[u]]) hson[u]=v;
}
}
void dfs2(int u,int anc) {
top[u]=anc,dfn[u]=++tim,pos[tim]=u;
if (hson[u]) dfs2(hson[u],anc);
for (int i=head[u];i;i=e[i].nxt)
if (e[i].v!=fa[u]&&e[i].v!=hson[u]) dfs2(e[i].v,e[i].v);
}
#define ls(o) t[o].ls
#define rs(o) t[o].rs
int rt[N],tot=0,lim;
struct node { ll sumv; int addv,ls,rs;} t[N*150];
void modify(int& o,int l,int r,int ql,int qr) {
if (o<=lim) t[++tot]=t[o],o=tot;
if (ql<=l&&r<=qr) { t[o].sumv+=pre[r]-pre[l-1],++t[o].addv; return; }
int mid=(l+r)>>1;
if (ql<=mid) modify(ls(o),l,mid,ql,qr);
if (qr>mid) modify(rs(o),mid+1,r,ql,qr);
t[o].sumv=t[ls(o)].sumv+t[rs(o)].sumv+t[o].addv*(pre[r]-pre[l-1]);
}
ll query(int o,int l,int r,int ql,int qr,int tag) {
if (!o) return tag*(pre[min(r,qr)]-pre[max(l,ql)-1]);
if (ql<=l&&r<=qr) return t[o].sumv+tag*(pre[r]-pre[l-1]);
int mid=(l+r)>>1; ll res=0;
if (ql<=mid) res+=query(t[o].ls,l,mid,ql,qr,tag+t[o].addv);
if (qr>mid) res+=query(t[o].rs,mid+1,r,ql,qr,tag+t[o].addv);
return res;
}
#undef ls
#undef rs
void modify(int u,int t) {
lim=tot;
while (u) {
modify(rt[t],1,n,dfn[top[u]],dfn[u]);
u=fa[top[u]];
}
}
ll query(int u,int t) {
ll res=t*dep[u]+sum[t];
while (u) {
res-=2*query(rt[t],1,n,dfn[top[u]],dfn[u],0);
u=fa[top[u]];
}
return res;
}
int main() {
n=read(),Q=read();
for (int i=1;i<=n;++i) p[i]=read();
for (int i=1;i<n;++i) {
int u=read(),v=read(),w=read();
addEdge(u,v,w),addEdge(v,u,w);
}
dfs1(1,0),dfs2(1,1);
for (int i=1;i<=n;++i) sum[i]=sum[i-1]+dep[p[i]];
for (int i=1;i<=n;++i) pre[i]=pre[i-1]+fw[pos[i]];
for (int i=1;i<=n;++i) rt[i]=rt[i-1],modify(p[i],i);
int lastans=0,cnt=0;
while (Q--) {
int op=read();
if (op==1) {
int l=read()^lastans,r=read()^lastans,u=read()^lastans;
ll ans=query(u,r)-query(u,l-1); printf("%lld\n",ans);
lastans=ans&1073741823;
} else {
int x=read()^lastans;
swap(p[x],p[x+1]),sum[x]=sum[x-1]+dep[p[x]];
if (++cnt==50000) {
cnt=tot=0;
for (int i=1;i<=n;++i) rt[i]=rt[i-1],modify(p[i],i);
}
else rt[x]=rt[x-1],modify(p[x],x);
}
}
return 0;
}