本文共 1168 字，大约阅读时间需要 3 分钟。
用LCT维护一下删除时间的最大生成树即可。当然也可以线段树分治。
#include #include #include #include #include #include #include using namespace std;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;}#define N 5010#define M 500010#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]int n,m,x[N+M],y[N+M],v[N+M],cnt;map f;struct edge{ int op,x,y,del;}q[M];struct data{ int ch[2],fa,rev,s;}tree[N+M];void up(int k){ tree[k].s=k; if (v[tree[lson].s] q[i].y) swap(q[i].x,q[i].y); if (q[i].op==0) f[1ll*q[i].x*m+q[i].y]=i; if (q[i].op==1) q[f[1ll*q[i].x*m+q[i].y]].del=i; } cnt=n; for (int i=0;i<=n;i++) tree[i].s=i,v[i]=M; for (int i=1;i<=m;i++) if (q[i].op==0&&q[i].del==0) q[i].del=M; for (int i=1;i<=m;i++) if (q[i].op==0) { if (findroot(q[i].x)!=findroot(q[i].y)) newpoint(q[i].x,q[i].y,q[i].del); else { int t=query(q[i].x,q[i].y); if (v[t]
转载于:https://www.cnblogs.com/Gloid/p/9383875.html