C++11(clang++ 3.9) 解法, 执行用时: 5473ms, 内存消耗: 48232K, 提交时间: 2018-04-07 15:48:33

#include<bits/stdc++.h>
using namespace std;

#define FOR(a,b,c) for(int a=(b),a##_end__=(c);a<a##_end__;++a)
#define DOR(a,b,c) for(int a=(b)-1,a##_end__=(c);a>=a##_end__;--a)
#define ll long long
template<class T>inline bool chkmin(T&a,T const&b){return a>b?a=b,true:false;}
template<class T>inline bool chkmax(T&a,T const&b){return a<b?a=b,true:false;}
const int M=100005;
const int S=1200;
const int N=M/S+5;
const int K=18;
struct Node{int u,v,x;}Q[M];
vector<int> E[M];
int Log2[M<<1],ST[M<<1][K],Eulorn[M],Dep[M];
int dfsv[M],Fa[M],P[M];
ll Val[N][M],dp[M],APS[M];
int n,m,w,q,Eulor_cnt,dfn_cnt;
 
void dfs(int u,int fa){
    ST[++Eulor_cnt][0]=u;
    dfsv[++dfn_cnt]=u;
    Eulorn[u]=Eulor_cnt;
    for(auto v:E[u]) if(v^fa){
        Fa[v]=u;
        Dep[v]=Dep[u]+1;
        dfs(v,u);
        ST[++Eulor_cnt][0]=u;
    }
}
inline int dep_min(int u,int v){return Dep[u]<Dep[v]?u:v;}
void ST_table(){
    FOR(k,1,K) FOR(i,1,(n<<1)-(1<<k)+1)
        ST[i][k]=dep_min(ST[i][k-1],ST[i+(1<<k-1)][k-1]);
}
inline int LCA(int u,int v){
    u=Eulorn[u],v=Eulorn[v];
    if(u>v) swap(u,v);
    int k=Log2[v-u+1];
    return dep_min(ST[u][k],ST[v-(1<<k)+1][k]);
}
inline ll Query(int u,int v,int x){
    int o=LCA(u,v),p=LCA(u,x),q=LCA(v,x),r=LCA(o,x);
    if(Dep[p]<Dep[q]) swap(p,q),swap(u,v);
    int Do=Dep[o],Du=Dep[u],Dv=Dep[v],Dp=Dep[p];
    int sum=Du+Dv-(Do<<1)+1;
    if(o!=r) return (ll)(Do+Dep[x]-(Dep[r]<<1))*sum+APS[Dv-Do]+APS[Du-Do];
    return (ll)(Dep[x]-Dp)*sum+APS[Du-Dp]+APS[Dp+Dv-(Do<<1)];
}
 
void build(Node *Q,ll *Val){
    FOR(i,0,M) P[i]=dp[i]=Val[i]=0;
    FOR(i,0,S){
        int u=Q[i].u,v=Q[i].v,x=LCA(u,v);
        P[u]++,P[v]++,P[x]--,P[Fa[x]]--;
    }
    DOR(i,n+1,1){
        int u=dfsv[i],v=Fa[u];
        P[v]+=P[u];
        dp[v]+=dp[u]+=P[u];
        Val[v]+=Val[u]+dp[u];
    }
    FOR(i,1,n+1){
        int u=dfsv[i];
        Val[u]=Val[Fa[u]]+dp[1]-(dp[u]<<1);
    }
}

int main(){
    FOR(i,2,M<<1) Log2[i]=Log2[i>>1]+1;
    FOR(i,0,M) APS[i]=(ll)i*(i+1)>>1;
    scanf("%d %d",&n,&q);
    FOR(i,1,n){
        int u,v;
        scanf("%d %d",&u,&v);
        E[u].push_back(v);
        E[v].push_back(u);
    }
    dfs(1,-1);
    ST_table();
    while(q--){
        int op,x,y,z;
        scanf("%d %d %d %d",&op,&x,&y,&z);
        if(op&1){
            Q[w++]={x,y,z};
            if(w%S==0){
            	auto cmp=[](Node A,Node B){return A.x<B.x;};
                sort(Q+m,Q+w,cmp);
                inplace_merge(Q,Q+m,Q+w,cmp);
                FOR(i,0,(m=w)/S) build(Q+i*S,Val[i]);
            }
        }
        else{
            ll res=0;
            FOR(i,m,w) if(x<=Q[i].x && Q[i].x<=y) res+=Query(Q[i].u,Q[i].v,z);
            int L=lower_bound(Q,Q+m,x,[](Node A,int x){return A.x<x;})-Q;
            int R=upper_bound(Q,Q+m,y,[](int x,Node A){return x<A.x;})-Q;
            if(L/S==R/S) FOR(i,L,R) res+=Query(Q[i].u,Q[i].v,z);
            else{
                FOR(i,L/S+1,R/S) res+=Val[i][z];
                FOR(i,L,L/S*S+S) res+=Query(Q[i].u,Q[i].v,z);
                FOR(i,R/S*S,R) res+=Query(Q[i].u,Q[i].v,z);
            }
            printf("%lld\n",res);
        }
    }
    return 0;
}