吼题啊
刚开始看上去又以为是LCT啥子的。
后来发现，TM是个图。
然后果断准备放弃，突然发现只有N个点N条边。
woc，这不就一个基环树上树链剖分吗。。。
关于基环树问题，相信大家都一定很有经验了吧，用个并查集找出多的边，然后把图分成一棵树和一条边，然后树上就树上做，多出来的边就可以另外处理。
关于边权转点权，直接在查询的最后减去LCA的点权就OK了，其他当成点权处理。
关于线段树，这个大家都会改吧。。。
关于修改操作，直接找出相应的点权，然后修改就行了，找点权记得先边的编号乘2
总之还是很简单的
下面可以看看代码注释：
#include<bits/stdc++.h>
#define maxn 4000001
#define L(x) (x<<1)
#define R(x) ((x<<1)|1)
using namespace std;
int tree[maxn],tag[maxn];
int rev[maxn],dep[maxn],size[maxn],seg[maxn],top[maxn],son[maxn],father[maxn];
int n,m,root,x,y,z,a[maxn],visx[maxn],visy[maxn],tot,mode;
int cnt,from[maxn],to[maxn],Next[maxn],head[maxn];
int Gx,Gy,Gz,Gd;
int fa[maxn],X[maxn],Y[maxn],Z[maxn];
int find(int x){
if(fa[x]==x)return x;
else return fa[x]=find(fa[x]);
}
bool merge(int x,int y){
int i=find(x),j=find(y);
if(i==j)return false;
fa[i]=j;return true;
}
void add(int x,int y){
cnt++;
from[cnt]=x;to[cnt]=y;
Next[cnt]=head[x];head[x]=cnt;
}
void update(int node,int begin,int end,int x,int y,int val){
if(begin>y||end<x)return;
if(begin>=x&&end<=y){
tree[node]=val;
return;
}else{
int mid=(begin+end)>>1;
if(x<=mid)update(L(node),begin,mid,x,y,val);
if(y>mid) update(R(node),mid+1,end,x,y,val);
tree[node]=tree[L(node)]+tree[R(node)];
}
}
int query(int node,int begin,int end,int x,int y){
if(begin>=x&&end<=y){
return tree[node];
}else{
int mid=(begin+end)>>1,sum=0;
if(x<=mid)sum+=query(L(node),begin,mid,x,y);
if(y>mid) sum+=query(R(node),mid+1,end,x,y);
return sum;
}
}
int dfs1(int x){
size[x]=1;
dep[x]=dep[father[x]]+1;
for(int i=head[x];i!=-1;i=Next[i]){
int v=to[i],big=0;
if(father[x]==v)continue;
father[v]=x;
big=dfs1(v);
size[x]+=big;
if(big>size[son[x]])son[x]=v;
}
return size[x];
}
void dfs2(int x){
if(son[x]){
seg[son[x]]=++seg[0];
top[son[x]]=top[x];
rev[seg[0]]=son[x];
dfs2(son[x]);
}
for(int i=head[x];i!=-1;i=Next[i]){
int v=to[i];
if(!top[v]){
seg[v]=++seg[0];
top[v]=v;
rev[seg[0]]=v;
dfs2(v);
}
}
}
int linkquery(int x,int y){
int fx=top[x],fy=top[y],ans=0;
while(fx!=fy){
if(dep[fx]<dep[fy])swap(x,y),swap(fx,fy);
ans+=query(1,1,seg[0],seg[fx],seg[x]);
x=father[fx];fx=top[x];
}
if(dep[x]>dep[y])swap(x,y);
ans+=query(1,1,seg[0],seg[x],seg[y]);
ans-=query(1,1,seg[0],seg[x],seg[x]);
return ans;
}
void change(int x,int y){ //修改边权
x*=2; //记得乘2
x=dep[from[x]]>dep[to[x]]?from[x]:to[x]; //因为边权钦定的是深度大的点
update(1,1,seg[0],seg[x],seg[x],y); //直接改
}
int main(){
memset(head,-1,sizeof(head));
scanf("%d%d",&n,&m);root=1;
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=n;i++){
scanf("%d%d%d",&x,&y,&z);
if(merge(x,y)){add(x,y),add(y,x);}
else Gx=x,Gy=y,Gz=z,Gd=i,cnt+=2; //并查集判多的边
X[i]=x;Y[i]=y;Z[i]=z;
}
dfs1(root);
seg[root]=++seg[0];
rev[seg[0]]=root;
top[root]=root;
dfs2(root);
for(int i=1;i<=n;i++)if(Gd!=i)change(i,Z[i]); //因为本人懒得写build，所以这样写
for(int i=1;i<=m;i++){
scanf("%d%d%d",&mode,&x,&y);
if(mode==1){
if(x==Gd)Gz=y; //如果是多余的边就直接改
else change(x,y); //不然就另外改
}else{
int ans;
ans=linkquery(x,y); //第一种情况，不经过多余的边
ans=min(ans,Gz+min(linkquery(x,Gx)+linkquery(Gy,y),linkquery(x,Gy)+linkquery(Gx,y))); //第二种情况，经过多余的边
printf("%d
",ans);
}
}
}