题解: 很显然的是这个图必然是一个树上套一个简单环 我们考虑到只有树的情况 那么直接树链剖分+线段树就好了 如果多加一条边 qko告诉我可以类似基环树那样 取出这个环 那么我们可以对于一个询问分类 如果在一颗子树上我们可以直接查询即可 如果绕过环相连 那么可以取两点对应环上的点取min 加上两个点在不同子树中的路径长度即可
#include <bits/stdc++.h>
#define ll long long
#define link(x) for(edge *j=h[x];j;j=j->next)
const int MAXN=1e5+10;
const int inf=1e9;
using namespace std;
struct FastIO
{
static const int S=200;
int wpos;
char wbuf[S];
FastIO():wpos(0){}
inline int xchar()
{
static char buf[S];
static int len=0,pos=0;
if(pos==len) pos=0,len=fread(buf,1,S,stdin);
if(pos==len) exit(0);
return buf[pos++];
}
inline int read()
{
int s=1,c=xchar(),x=0;
while(c<=32) c=xchar();
if(c=='-') s=-1,c=xchar();
for(;'0'<=c&&c<='9';c=xchar()) x=x*10+c-'0';
return x*s;
}
~FastIO()
{
if(wpos) fwrite(wbuf,1,wpos,stdout),wpos=0;
}
}io;
int n,m;
int F[MAXN],f[MAXN],b[MAXN];
int dep[MAXN],fa[MAXN],son[MAXN],num[MAXN],pos[MAXN],key[MAXN];
bool vis[MAXN],vi[MAXN];
int v1[MAXN];
struct edge{int t,id;ll v;bool f;edge*next,*rev;}e[MAXN<<2],*h[MAXN],*o=e;
void add(int x,int y,ll v,int p){o->v=v;o->t=y;o->id=p;o->next=h[x];h[x]=o++;}
int __v[MAXN];
int find1(int x){
if(x==F[x])return x;
else return F[x]=find1(F[x]);
}
int _x,tot,c[MAXN],_t;
void _dfs(int x){
__v[x]++;
link(x)if(!j->f){
j->f=j->rev->f=true;
if(__v[j->t]){_t=j->t;c[++tot]=x;vis[x]=1;return;}
else _dfs(j->t);
if(_t){c[++tot]=x;vis[x]=1;break;}
}
if(_t==x)_t=0;
}
void dfs(int v,int pre,int deep){
dep[v]=deep+1;fa[v]=pre;num[v]=1;
link(v)if(j->t!=pre&&!vis[j->t]){
F[j->t]=v;
key[j->t]=j->v;
pos[j->id]=j->t;
dfs(j->t,v,deep+1);
num[v]+=num[j->t];
if(son[v]==-1||num[j->t]>num[son[v]])son[v]=j->t;
}
}
int p[MAXN],fp[MAXN],tp[MAXN],cnt;
void dfs1(int v,int td){
p[v]=++cnt;fp[p[v]]=v;tp[v]=td;
if(son[v]!=-1)dfs1(son[v],td);
link(v)if(j->t!=fa[v]&&j->t!=son[v]&&!vis[j->t])dfs1(j->t,j->t);
}
ll sum[MAXN<<2];
void built(int rt,int l,int r){
if(l==r){sum[rt]=key[fp[l]];return ;}
int mid=(l+r)>>1;
built(rt<<1,l,mid);
built(rt<<1|1,mid+1,r);
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
ll ans;
void querty(int rt,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){ans+=sum[rt];return ;}
int mid=(l+r)>>1;
if(ql<=mid)querty(rt<<1,l,mid,ql,qr);
if(qr>mid)querty(rt<<1|1,mid+1,r,ql,qr);
}
void update(int rt,int l,int r,int t,int vul){
if(l==r){sum[rt]=vul;return ;}
int mid=(l+r)>>1;
if(t<=mid)update(rt<<1,l,mid,t,vul);
else update(rt<<1|1,mid+1,r,t,vul);
sum[rt]=sum[rt<<1]+sum[rt<<1|1];
}
ll Sum(int u,int v){
int uu=tp[u];int vv=tp[v];
ll ans1=0;
while(uu!=vv){
if(dep[uu]<dep[vv]){swap(uu,vv);swap(u,v);}
ans=0;querty(1,1,n,p[uu],p[u]);ans1+=ans;
u=fa[uu];uu=tp[u];
}
if(dep[u]>dep[v])swap(u,v);
//cout<<son[u]<<" "<<u<<" "<<v<<" "<<p[son[u]]<<" "<<p[v]<<" "<<ans1<<endl;
if(u!=v)ans=0,querty(1,1,n,p[son[u]],p[v]),ans1+=ans;
return ans1;
}
ll sum1[MAXN<<2];
int get_id(int x){return x&(-x);}
void update1(int x,int vul){
//cout<<x<<" "<<vul<<endl;
for(int i=x;i<=2*n;i+=get_id(i))sum1[i]+=vul;
}
ll querty1(int x){
ll ans1=0;
for(int i=x;i>0;i-=get_id(i))ans1+=sum1[i];
return ans1;
}
int main(){
//freopen("k.out","w",stdout);
int _=io.read();//scanf("%d",&_);
while(_--){
n=io.read();m=io.read();memset(e,0,sizeof(e));memset(h,0,sizeof(h));o=e;
memset(vis,0,sizeof(vis));memset(sum1,0,sizeof(sum1));memset(sum,0,sizeof(sum));
memset(vi,0,sizeof(vi));
memset(__v,0,sizeof(__v));
for(int i=1;i<=n;i++)F[i]=i,son[i]=-1,pos[i]=n+1;
int u,v,vul;tot=0;cnt=0;
for(int i=1;i<=n;i++)u=io.read(),v=io.read(),vul=io.read(),add(u,v,vul,i),add(v,u,vul,i),h[u]->rev=h[v],h[v]->rev=h[u];
for(int i=1;i<=n;i++)if(!__v[i])_dfs(i);
for(int i=1;i<=tot;i++)v1[c[i]]=i;
for(int i=1;i<=tot;i++)c[i+tot]=c[i],v1[c[i+tot]]=v1[c[i]];
tot*=2;
for(int k=1;k<=tot-1;k++)
link(c[k])if(j->t==c[k+1])b[k+1]=j->v,pos[j->id]=min(pos[j->id],k+1),vi[j->id]=1;
for(int k=1;k<=tot;k++)update1(k,b[k]);
tot/=2;
for(int i=1;i<=tot;i++){dfs(c[i],0,0);dfs1(c[i],c[i]);}
//for(int i=1;i<=n;i++)cout<<key[i]<<" ";
// cout<<endl;
built(1,1,n);
int op,x,y;
for(int i=1;i<=m;i++){
op=io.read();x=io.read();y=io.read();
if(op==0){
if(vi[x]){
x=pos[x];
update1(x,-1*b[x]);update1(x,y);
update1(x+tot,-1*b[x]);update1(x+tot,y);
b[x]=y;
}
else update(1,1,n,p[pos[x]],y);
}
else{
int t1=find1(x);int t2=find1(y);
if(t1==t2)printf("%lld
",Sum(x,y));
else{
ll ans1=Sum(x,t1);ans1+=Sum(y,t2);
t1=v1[t1];t2=v1[t2];
if(t1>t2)swap(t1,t2);
ans1+=min(querty1(t2)-querty1(t1),querty1(t1+tot)-querty1(t2));
printf("%lld
",ans1);
}
}
}
}
return 0;
}