动态维护一下最小生成树即可.
#include<bits/stdc++.h>
#define ll long long
#define maxn 1000000
#define inf 1000000000000
using namespace std;
void setIO(string s)
{
string in=s+".in",out=s+".out";
freopen(in.c_str(),"r",stdin);
// freopen(out.c_str(),"w",stdout);
}
struct Union
{
int p[maxn];
void init()
{
for(int i=0;i<maxn;++i) p[i]=i;
}
int find(int x)
{
return p[x]==x?x:p[x]=find(p[x]);
}
void merge(int a,int b)
{
int x=find(a),y=find(b);
if(x==y) return ;
p[x]=y;
}
}ut;
struct LCT
{
#define lson ch[x][0]
#define rson ch[x][1]
int f[maxn],ch[maxn][2],sta[maxn],rev[maxn];
ll w[maxn],val[maxn],sumv[maxn],minv[maxn];
int isRoot(int x)
{
return !(ch[f[x]][0]==x||ch[f[x]][1]==x);
}
int get(int x)
{
return ch[f[x]][1]==x;
}
void pushdown(int x)
{
if(!x||!rev[x]) return;
mark(lson), mark(rson),rev[x]^=1;
}
void mark(int x)
{
if(!x) return;
swap(lson,rson),rev[x]^=1;
}
void pushup(int x)
{
if(!x) return;
sumv[x]=sumv[lson]+sumv[rson]+val[x];
minv[x]=min(min(minv[lson],minv[rson]),w[x]);
}
void rotate(int x)
{
int old = f[x], fold = f[old], which = get(x);
if(!isRoot(old)) ch[fold][ch[fold][1] == old] = x;
ch[old][which] = ch[x][which ^ 1], f[ch[old][which]] = old;
ch[x][which ^ 1] = old, f[old] = x, f[x] = fold;
pushup(old), pushup(x);
}
void splay(int x)
{
int u=x,v=0,fa;
sta[++v]=u;
while(!isRoot(u)) sta[++v]=f[u],u=f[u];
while(v) pushdown(sta[v--]);
for(u=f[u];(fa=f[x])!=u;rotate(x))
if(f[fa]!=u)
rotate(get(fa)==get(x)?fa:x);
}
void Access(int x)
{
int t=0;
while(x) splay(x),rson=t,pushup(x),t=x,x=f[x];
}
void MakeRoot(int x)
{
Access(x),splay(x), mark(x);
}
void link(int a,int b)
{
MakeRoot(a),f[a]=b;
}
int FindRoot(int x)
{
Access(x), splay(x);
while(lson) x=lson;
return x;
}
void split(int x,int y)
{
MakeRoot(x), Access(y), splay(y);
}
void cut(int a,int b)
{
split(a,b),ch[b][0]=f[a]=0, pushup(b);
}
int find(int x)
{
if(w[x]==minv[x]) return x;
return minv[lson]==minv[x]?find(lson):find(rson);
}
}tree;
int h1[maxn],h2[maxn];
char opt[20];
#define idx(i) (i+n)
int main()
{
// setIO("input");
ll t;
int n,m,id,u,v,l,cur;
scanf("%d%d",&n,&m);
for(int i=0;i<=n;++i) tree.w[i]=inf;
tree.minv[0]=inf;
ut.init();
while(m--)
{
scanf("%s",opt);
switch(opt[0])
{
case 'f' :
{
scanf("%d%d%d%lld%d",&id,&u,&v,&t,&l);
++id,++u,++v;
h1[cur=idx(id)]=u,h2[idx(id)]=v;
if(ut.find(u)!=ut.find(v))
{
ut.merge(u,v);
tree.val[cur]=l,tree.w[cur]=t;
ut.merge(u,cur),ut.merge(v,cur);
tree.link(u,cur), tree.link(v,cur);
}
else
{
tree.split(u,v);
if(tree.minv[v] < t)
{
int k=tree.find(v);
tree.cut(k, h1[k]), tree.cut(k, h2[k]);
tree.val[cur=idx(id)]=l,tree.w[cur]=t;
ut.merge(u,cur), ut.merge(v,cur);
tree.link(u,cur),tree.link(v,cur);
}
}
break;
}
case 'm' :
{
scanf("%d%d",&u,&v);
++u,++v;
if(ut.find(u)!=ut.find(v))
{
printf("-1
");
}
else
{
tree.split(u,v), printf("%lld
",tree.sumv[v]);
}
break;
}
case 'c' :
{
scanf("%d%d",&id,&l);
++id;
tree.Access(cur=idx(id)),tree.val[cur]=l,tree.pushup(cur);
break;
}
}
}
return 0;
}