[toc]

题目链接：Luogu P4949

题解

思路

显然，一个 $ n $ 个点 $ n $ 条边的无向连通图是一颗基环树，那么这道题就非常简单，树链剖分并特判即可。

代码

渐进时间复杂度为 $ \Theta ( n \alpha (n) + n \log _ {2} ^ {2} n ) $，其中的 $ \alpha (n) $ 为并查集的渐进时间复杂度，因为后面的代码只用了路径压缩的优化，所以 $ \alpha (n) = \Theta ( \log _ {2} n ) $。

#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
typedef unsigned long long ull;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
    reg bool f=false;
    reg char ch=getchar();
    reg int res=0;
    while(ch<'0'||'9'<ch)f|=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
    return f?-res:res;
}

const int MAXN=100006+5; // n 的范围

inline void Read(void);
inline void Work(void);

int main(void){
    Read();
    Work();
    return 0;
}

int n,m;
int cnt,head[MAXN],to[MAXN<<1],w[MAXN<<1],Next[MAXN<<1];
int u[MAXN],v[MAXN],W[MAXN];

inline void Add_Edge(reg int u,reg int v,reg int len){
    Next[++cnt]=head[u];
    to[cnt]=v;
    w[cnt]=len;
    head[u]=cnt;
    return;
}

struct UnionFind{ // 并查集
    int ID[MAXN];
    inline void Init(reg int size){ // 并查集的初始化
        for(reg int i=1;i<=size;++i)
            ID[i]=i;
        return;
    }
    inline int find(reg int x){
        if(x==ID[x])
            return x;
        else
            return ID[x]=find(ID[x]); // 路径压缩
    }
    inline void merge(reg int a,reg int b){ // 合并
        reg int ra=find(a),rb=find(b);
        if(ra!=rb)
            ID[rb]=ra;
        return;
    }
    inline bool search(reg int a,reg int b){ // 是否连接
        return find(a)==find(b);
    }
};

int end;
UnionFind U;

inline void Read(void){
    n=read(),m=read();
    U.Init(n); // 初始化
    for(reg int i=1;i<=n;++i){
        u[i]=read(),v[i]=read(),W[i]=read();
        if(!U.search(u[i],v[i])){ // 正常的边
            U.merge(u[i],v[i]);
            Add_Edge(u[i],v[i],W[i]);
            Add_Edge(v[i],u[i],W[i]);
        }
        else // 多出的边
            end=i;
    }
    return;
}

int fa[MAXN],dep[MAXN];
int size[MAXN],son[MAXN];
int val[MAXN];

inline void DFS1(reg int ID,reg int father){
    size[ID]=1;
    fa[ID]=father;
    dep[ID]=dep[father]+1;
    for(reg int i=head[ID];i;i=Next[i])
        if(to[i]!=father){
            val[to[i]]=w[i]; // 边权变为儿子的点权
            DFS1(to[i],ID);
            size[ID]+=size[to[i]];
            if(size[to[i]]>size[son[ID]])
                son[ID]=to[i]; // 求重儿子
        }
    return;
}

int DFN,dfn[MAXN],rank[MAXN];
int top[MAXN];

inline void DFS2(reg int ID,reg int father,reg int topf){
    top[ID]=topf;
    dfn[ID]=++DFN; // DFS 序
    rank[dfn[ID]]=ID; // 逆 DFS 序
    if(!son[ID])
        return;
    DFS2(son[ID],ID,topf); // 先遍历重儿子
    for(reg int i=head[ID];i;i=Next[i])
        if(to[i]!=father&&to[i]!=son[ID])
            DFS2(to[i],ID,to[i]); // 遍历其他儿子
    return;
}

struct SegmentTree{ // 支持单点修改，区间查询和的线段树
    #define lson ( (k) << 1 )
    #define rson ( (k) << 1 | 1 )
    #define mid ( ( (l) + (r) ) >> 1 )
    struct Node{
        int sum;
        inline Node(reg int sum=0):sum(sum){
            return;
        }
    };
    Node unit[MAXN<<2];
    inline void pushup(reg int k){
        unit[k]=Node(unit[lson].sum+unit[rson].sum);
        return;
    }
    inline void Build(reg int k,reg int l,reg int r,reg int a[],reg int rank[]){
        if(l==r){
            unit[k]=Node(a[rank[l]]);
            return;
        }
        Build(lson,l,mid,a,rank);
        Build(rson,mid+1,r,a,rank);
        pushup(k);
        return;
    }
    inline void Update(reg int k,reg int l,reg int r,reg int pos,reg int val){
        if(l==r){
            unit[k].sum=val;
            return;
        }
        if(pos<=mid)
            Update(lson,l,mid,pos,val);
        else
            Update(rson,mid+1,r,pos,val);
        pushup(k);
        return;
    }
    inline int Query(reg int k,reg int l,reg int r,reg int L,reg int R){
        if(L<=l&&r<=R)
            return unit[k].sum;
        reg int res=0;
        if(L<=mid)
            res+=Query(lson,l,mid,L,R);
        if(R>mid)
            res+=Query(rson,mid+1,r,L,R);
        return res;
    }
    #undef lson
    #undef rson
    #undef mid
};

SegmentTree T;

inline int Query(int x,int y){
    reg int res=0;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        res+=T.Query(1,1,n,dfn[top[x]],dfn[x]); // 查询
        x=fa[top[x]]; // 往上条
    }
    if(dep[x]>dep[y])
        swap(x,y);
    if(x!=y)
        res+=T.Query(1,1,n,dfn[x]+1,dfn[y]); // 防止多加
    return res;
}

inline void Work(void){
    DFS1(1,0);
    DFS2(1,0,1);
    T.Build(1,1,n,val,rank); // 建树
    while(m--){
        static int opt,x,y;
        opt=read(),x=read(),y=read();
        if(opt==1){
            if(x!=end){
                reg int son=dep[u[x]]<dep[v[x]]?v[x]:u[x];
                W[x]=y;
                T.Update(1,1,n,dfn[son],y);
            }
            else
                W[end]=y;
        }
        else if(opt==2){
            int ans=Query(x,y);
            int ans1=Query(x,u[end])+W[end]+Query(v[end],y); // 情况 1
            int ans2=Query(x,v[end])+W[end]+Query(u[end],y); // 情况 2
            // 特判
            printf("%d\n",min(ans,min(ans1,ans2)));
        }
    }
    return;
}