C++11(clang++ 3.9) 解法, 执行用时: 3046ms, 内存消耗: 180044K, 提交时间: 2017-12-18 16:29:52

#include <bits/stdc++.h>
#define LL long long
using namespace std;
int L,R,X,Y,Z,U,V,t,op,n,m,aa[200005],on[200005],F[200005][20],G[200005][20],H[200005],zz;
vector <int> a[200005],b[200005];
LL W[200005][20],h[200005],ans;
struct O{int x; LL s;};
vector <O> P[400005];
bool operator<(O a,O b){return a.x<b.x;}
void QH(int x,int fa){
    int z=-1,y;
    for (int i=0;i<a[x].size();++i)
    if (a[x][i]!=fa){
        y=a[x][i]; QH(y,x);
        for (int j=0;j<20;++j){
            if (F[y][j]&F[x][j]) z=max(z,j);
            F[x][j]|=F[y][j];
        }
    }
    for (++z;F[x][z];++z); F[x][z]=1;
    H[x]=z; for (--z;~z;--z) F[x][z]=0;
    zz=max(zz,H[x]);
}
void dfs(int x,int y){
    F[x][Z]=U; W[x][Z]=h[x]; G[x][Z]=V;
    P[U].push_back((O){on[x],h[x]});
    P[V].push_back((O){on[x],h[x]});
    for (int i=0;i<a[x].size();++i)
    if (a[x][i]!=y&&H[a[x][i]]<Z){
        h[a[x][i]]=h[x]+b[x][i];
        dfs(a[x][i],x);
    }
}
LL qiu(int u,LL w){
    int p=lower_bound(P[u].begin(),P[u].end(),(O){L,0})-P[u].begin()-1,
        q=upper_bound(P[u].begin(),P[u].end(),(O){R,0})-P[u].begin()-1;
    return (q>=0?P[u][q].s:0)-(p>=0?P[u][p].s:0)+w*(q-p);
}
void mody(int u,int v){
    if (u==v&&u){
        O x={on[X],0};
        int t=lower_bound(P[u].begin(),P[u].end(),x)-P[u].begin();
        LL s=t?P[u][t-1].s:0;
        P[u][t+1].s-=P[u][t].s; P[u][t].s-=s;
        swap(P[u][t].s,P[u][t+1].s);
        P[u][t].s+=s; P[u][t+1].s+=P[u][t].s;
        return;
    }
    if (u){
        O x={on[X],0};
        int t=lower_bound(P[u].begin(),P[u].end(),x)-P[u].begin();
        ++P[u][t].x;
    }
    if (v){
        O x={on[Y],0};
        int t=lower_bound(P[v].begin(),P[v].end(),x)-P[v].begin();
        --P[v][t].x;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i) scanf("%d",&aa[i]),on[aa[i]]=i;
    for (int i=1;i<n;++i){
        scanf("%d%d%d",&X,&Y,&Z);
        a[X].push_back(Y); b[X].push_back(Z);
        a[Y].push_back(X); b[Y].push_back(Z);
    }
    QH(1,0); memset(F,0,sizeof F);
    for (int i=1;i<=n;++i){
        X=aa[i]; Z=H[X]; U=++t; h[X]=0;
        P[U].push_back((O){on[X],0}); F[X][Z]=U;
        for (int j=0;j<a[X].size();++j)
        if (H[a[X][j]]<Z){
            h[a[X][j]]=b[X][j];
            V=++t; dfs(a[X][j],X);
            sort(P[V].begin(),P[V].end());
            for (int k=1;k<P[V].size();++k)
                P[V][k].s+=P[V][k-1].s;
        }
        sort(P[U].begin(),P[U].end());
        for (int k=1;k<P[U].size();++k)
            P[U][k].s+=P[U][k-1].s;
    }
    while (m--){
        scanf("%d",&op);
        if (op==1){
            scanf("%d%d%d",&L,&R,&X); ans=0;
            for (int i=H[X];i<=zz;++i)
            ans+=qiu(F[X][i],W[X][i])-qiu(G[X][i],W[X][i]);
            printf("%lld\n",ans);
        }else{
            scanf("%d",&Z); X=aa[Z]; Y=aa[Z+1];
            swap(aa[Z],aa[Z+1]);
            for (int i=0;i<=zz;++i){
                mody(F[X][i],F[Y][i]);
                mody(G[X][i],G[Y][i]);
            }
            swap(on[X],on[Y]);
        }
    }
    return 0;
}