Description
给出\(n\)个点，\(m\)条边的无向图
每条边有两个权值\(a\)和\(b\)
定义一条路径的代价为边中最大的\(a\)值和最大的\(b\)值之和
求从\(1\)到\(n\)的最小代价
Solution
把边按照\(a\)来排序，然后动态维护原树关于\(b\)的最小生成树，考虑用\(lct\)来维护
Code
#includeusing namespace std;int read(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return x*f;}#define reg registerconst int MN=1.5e5+5,MM=1e5+5,inf=0x3f3f3f3f;struct LCT{ int c[MN][2],fa[MN],w[MN],X[MN],st[MN],N,a[MN],b[MN]; bool rev[MN]; bool nrt(int x){return c[fa[x]][0]==x||c[fa[x]][1]==x;} void Rev(int x){rev[x]^=1;std::swap(c[x][0],c[x][1]);} bool get(int x){return c[fa[x]][1]==x;} void up(int x) { X[x]=x; if(w[X[c[x][0]]]>w[X[x]]) X[x]=X[c[x][0]]; if(w[X[c[x][1]]]>w[X[x]]) X[x]=X[c[x][1]]; } inline void down(int x){if(x&&rev[x])Rev(c[x][0]),Rev(c[x][1]),rev[x]=0;} void rtt(int x) { int y=fa[x],z=fa[y],l=get(x),r=l^1;if(nrt(y))c[z][get(y)]=x;fa[x]=z; c[y][l]=c[x][r];fa[c[x][r]]=y;c[x][r]=y;fa[y]=x;up(y); } void Splay(int x) { int i,top;st[top=1]=x; for(i=x;nrt(i);i=fa[i])st[++top]=fa[i];//wrong af for(;top>0;--top)down(st[top]); for(;nrt(x);rtt(x)) if(nrt(fa[x])) rtt(get(x)^get(fa[x])?x:fa[x]); up(x); } void acs(int x){for(int i=0;x;x=fa[i=x])Splay(x),c[x][1]=i,up(x);}//wrong af void mkrt(int x){acs(x);Splay(x);Rev(x);} int fdrt(int x){acs(x);Splay(x);for(;c[x][0];down(c[x][0]),x=c[x][0]);Splay(x);return x;}//forget to Splay af void link(int x,int y){mkrt(x);fa[x]=y;} void cut(int x,int y){mkrt(x);acs(y);Splay(y);c[y][0]=fa[x]=0,up(y);}//forget to up af void ins(int x,int y,int B) { mkrt(x); if(fdrt(y)^x){w[++N]=B;link(a[N]=x,N);link(b[N]=y,N);return;} mkrt(x);acs(y);Splay(y); if(B>=w[X[y]]) return; int t=X[y];cut(t,a[t]);cut(t,b[t]); w[++N]=B;link(a[N]=x,N);link(b[N]=y,N); } int que(int x,int y) { mkrt(x);if(fdrt(y)^x) return inf; acs(y);Splay(y);return w[X[y]]; }}lct;struct edge{int u,v,a,b;}e[MM];inline bool cmp(const edge&x,const edge&y){return x.a
Blog来自PaperCloud，未经允许，请勿转载，TKS！