类似于瓶颈路，满足条件的路径一定在温度的最大生成树上，那么就是一个LCT维护MST的裸题了。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; #define ll long long #define N 100010 #define M 300010 #define inf 1000000001 #define lson tree[k].ch[0] #define rson tree[k].ch[1] #define lself tree[tree[k].fa].ch[0] #define rself tree[tree[k].fa].ch[1] char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar(); return x*f; } int n,m,cnt,w[N+M][2],id[M],temp[N+M]; struct data{int ch[2],fa,rev,len,sum,id; }tree[N+M]; void up(int k) { tree[k].sum=tree[lson].sum+tree[rson].sum+tree[k].len; tree[k].id=k; if (temp[tree[lson].id]<temp[tree[k].id]) tree[k].id=tree[lson].id; if (temp[tree[rson].id]<temp[tree[k].id]) tree[k].id=tree[rson].id; } void rev(int k){if (k) swap(lson,rson),tree[k].rev^=1;} void down(int k){if (tree[k].rev) rev(lson),rev(rson),tree[k].rev=0;} bool isroot(int k){return lself!=k&&rself!=k;} int whichson(int k){return rself==k;} void push(int k){if (!isroot(k)) push(tree[k].fa);down(k);} void move(int k) { int fa=tree[k].fa,gf=tree[fa].fa,p=whichson(k); if (!isroot(fa)) tree[gf].ch[whichson(fa)]=k;tree[k].fa=gf; tree[fa].ch[p]=tree[k].ch[!p],tree[tree[k].ch[!p]].fa=fa; tree[k].ch[!p]=fa,tree[fa].fa=k; up(fa),up(k); } void splay(int k) { push(k); while (!isroot(k)) { int fa=tree[k].fa; if (!isroot(fa)) if (whichson(k)^whichson(fa)) move(k); else move(fa); move(k); } } void access(int k){for (int t=0;k;t=k,k=tree[k].fa) splay(k),tree[k].ch[1]=t,up(k);} int findroot(int k){access(k),splay(k);for (;lson;k=lson) down(k);splay(k);return k;} void makeroot(int k){access(k),splay(k),rev(k);} void link(int x,int y){makeroot(x),tree[x].fa=y;} void cut(int x,int y){makeroot(x),access(y),splay(y),tree[y].ch[0]=tree[x].fa=0,up(y);} int queryid(int x,int y){makeroot(x),access(y),splay(y);return tree[y].id;} int querylen(int x,int y){makeroot(x),access(y),splay(y);return tree[y].sum;} int main() { #ifndef ONLINE_JUDGE freopen("bzoj4736.in","r",stdin); freopen("bzoj4736.out","w",stdout); const char LL[]="%I64d "; #else const char LL[]="%lld "; #endif n=read(),m=read(); for (int i=0;i<=n;i++) temp[i]=inf,tree[i].id=i;cnt=n; for (int i=1;i<=m;i++) { char c=getc(); if (c=='f') { int u=read(),x=read()+1,y=read()+1,t=read(),l=read(); if (findroot(x)==findroot(y)) { int p=queryid(x,y); if (temp[p]>=t) continue; cut(p,w[p][0]),cut(p,w[p][1]); w[p][0]=w[p][1]=0; } id[u]=++cnt;temp[id[u]]=t,tree[id[u]].len=tree[id[u]].sum=l,tree[id[u]].id=id[u],w[id[u]][0]=x,w[id[u]][1]=y; link(id[u],x),link(id[u],y); } if (c=='m') { int x=read()+1,y=read()+1; if (findroot(x)!=findroot(y)) printf("-1 "); else printf("%d ",querylen(x,y)); } if (c=='c') { int u=read(),l=read(); if (w[id[u]][0]) { cut(id[u],w[id[u]][0]),cut(id[u],w[id[u]][1]); tree[id[u]].len=tree[id[u]].sum=l; link(id[u],w[id[u]][0]),link(id[u],w[id[u]][1]); } } } return 0; }