题意

给n个点和n条边的图，有两种操作，一种修改边权，另一种查询u到v的最短路。

分析

n个点和n条边，实际上是一棵树+一个环，如果仅仅是一棵树，那么这题就是树链剖分的模板题了。

对于环来说，可以考虑先把环中一条边提取出来，然后树链剖分，修改时用线段树，单点修改和区间求和。

查询时就考虑三种情况，u走树上到v，从u经过提取出来的边再到v（两种），取最小值。

至于取出环上一条边，用并查集搞搞。

#include
     
      #define mem(a,b) memset(a,b,sizeof(a))using namespace std;typedef long long ll;const int inf = 0x3f3f3f3f;const int maxn = 2e5+5;struct side {    int u,v,w;    int ne;} s[maxn];struct edge {    int l,r;    ll v;} e[maxn<<2];int n,q;int head[maxn],len;int val[maxn],hold[maxn],pre[maxn];int deep[maxn],fa[maxn],ve[maxn],son[maxn],top[maxn],p[maxn],fp[maxn],sz;void add(int u,int v,int w) {    s[len].u = u;    s[len].v = v;    s[len].w = w;    s[len].ne = head[u];    head[u] = len++;}int find(int x) {    return pre[x] == x?x:pre[x] = find(pre[x]);}void dfs1(int u,int p,int d) {    deep[u] = d;    fa[u] = p;    ve[u] = 1;    son[u] = -1;    for(int i = head[u]; i!= -1; i = s[i].ne) {        if(s[i].v == p) continue;        val[s[i].v] = s[i].w; //把边权值赋给相连的点        hold[i>>1] = s[i].v;//这条边的权值被哪个点掌握着        dfs1(s[i].v,u,d+1);        ve[u]+= ve[s[i].v];        if(son[u] == -1||ve[s[i].v]> ve[son[u]])            son[u] = s[i].v;    }    return ;}void dfs2(int u,int sp) {    top[u] = sp;    p[u] = ++sz;    fp[p[u]] = u;    if(son[u] == -1) return ;    dfs2(son[u],sp);    for(int i = head[u]; i!= -1; i = s[i].ne) {        if(s[i].v == son[u]||s[i].v == fa[u]) continue;        dfs2(s[i].v,s[i].v);    }    return ;}void build(int i,int l,int r) {    e[i].l = l;    e[i].r = r;    if(l == r) {        e[i].v = val[fp[l]];        return ;    }    int mid = (l+r)>>1;    build(i<<1,l,mid);    build(i<<1|1,mid+1,r);    e[i].v = e[i<<1].v+e[i<<1|1].v;}void modify(int i,int pos,int v) {    if(pos> e[i].r||pos< e[i].l) return ;    if(e[i].l == e[i].r) {        e[i].v = v;        return ;    }    modify(i<<1,pos,v);    modify(i<<1|1,pos,v);    e[i].v = e[i<<1].v+e[i<<1|1].v;}ll query(int i,int l,int r) {    if(e[i].r< l||e[i].l> r) return 0;    if(e[i].l>= l&&e[i].r<= r) return e[i].v;    return query(i<<1,l,r)+query(i<<1|1,l,r);}ll demand(int x,int y) {    int fx = top[x];    int fy = top[y];    ll ans = 0;    while(fx!= fy) {        if(deep[fx]< deep[fy]) {            swap(fx,fy);            swap(x,y);        }        ans+= query(1,p[fx],p[x]);        x = fa[fx];        fx = top[x];    }    if(x == y) return ans;    if(deep[x]> deep[y]) swap(x,y);    ans+= query(1,p[son[x]],p[y]);    return ans;}void init() {    sz = len = 0;    mem(head,-1);    for(int i = 0; i<= n; i++) pre[i] = i;}int main() {    int t;    cin>>t;    while(t--) {        int su,sv,sc,ss;        scanf("%d %d",&n,&q);        init();        for(int i = 1; i<= n; i++) {            int u,v,w;            scanf("%d %d %d",&u,&v,&w);            int fx = find(u);            int fy = find(v);            if(fx == fy) {                len+= 2;                ss = i;                su = u;                sv = v;                sc = w;                continue;            } else                pre[fy] = fx;            add(u,v,w);            add(v,u,w);        }        dfs1(1,-1,1);        dfs2(1,1);        build(1,1,n);        while(q--) {            int o,x,y;            scanf("%d %d %d",&o,&x,&y);            if(o == 0) {                x--;                if(x == ss) {                    sc = y;                    continue;                }                modify(1,p[hold[x]],y);            } else {                ll ans;                ans = sc+min(demand(x,su)+demand(y,sv),demand(x,sv)+demand(y,su));                ans = min(ans,demand(x,y));                printf("%lld\n",ans);            }        }    }    return 0;}