这是我在线下搞出的Ans:
第三行是256.
这是在IDE上跑
第三行就是309……
下附代码:
#include <map>
#include <cstdio>
#include <algorithm>
const int maxn = 3e5+5,maxm = 1e6+5;
inline int max(int a,int b) {
return a>b?a:b;
}
inline void swap(int &a,int &b) {
a ^= b,b ^= a,a ^= b;
}
int n,m,q;
struct Edge {
int from,to,val;
bool operator <(Edge b)const {return val<b.val;}
} e[maxm];
int ans[maxn],anscnt;
struct Shik {
int ty,x,y;
bool operator <(Shik b)const {return x==b.x?y<b.y:x<b.x;}
} op[maxn];
std :: map<Shik,int> del,eval,eid;
int siz[maxn],ch[maxn][2],fa[maxn],rev[maxn],maxx[maxn],maxxid[maxn],val[maxn];
inline int identify(int x) {
return ch[fa[x]][1] == x;
}
inline int nroot(int x) {
return ch[fa[x]][0] == x || ch[fa[x]][1] == x;
}
inline void pushup(int x) {
// printf("ID:%d %d %d\n",x,ch[x][0],ch[x][1]);
// printf("pushup:%d %d %d\n",maxx[ch[x][0]],maxx[ch[x][1]],val[x]);
maxx[x] = max(maxx[ch[x][0]],max(maxx[ch[x][1]],val[x]));
if(maxx[x] == maxx[ch[x][0]])maxxid[x] = maxxid[ch[x][0]];
else if(maxx[x] == maxx[ch[x][1]])maxxid[x] = maxxid[ch[x][1]];
else maxxid[x] = x;
// printf("in ph:%d %d\n",maxx[x],maxxid[x]);
}
inline void grev(int x) {
rev[x] ^= 1,swap(ch[x][0],ch[x][1]);
}
inline void pushdown(int x) {
if(rev[x])rev[x] = 0,grev(ch[x][0]),grev(ch[x][1]);
}
inline void connect(int x,int F,int sid) {
ch[F][sid] = x,fa[x] = F;
}
inline void rotate(int x) {
int y = fa[x],z = fa[y],xy = identify(x),yz = identify(y),nry = nroot(y);
connect(ch[x][xy^1],y,xy),connect(y,x,xy^1),fa[x] = z;
if(nry)ch[z][yz] = x;
pushup(y),pushup(x);
}
void ptag(int x) {
if(nroot(x))ptag(fa[x]);
pushdown(x);
}
inline void Splay(int x) {
ptag(x);
while(nroot(x)) {
int y=fa[x];
// printf("Spaly:%d %d\n",x,y);
// system("pause");
if(nroot(y))identify(x)^identify(y) ? rotate(x) : rotate(y);
rotate(x);
}
}
inline void access(int x) {
for(int y=0; x; x=fa[y=x])Splay(x),ch[x][1] = y,pushup(x);
}
inline void evert(int x) {
access(x);
Splay(x);
grev(x);
}
inline void split(int x,int y) {
evert(x),access(y),Splay(y);
}
inline void link(int x,int y) {
evert(x),fa[x] = y;
}
inline void cut(int x,int y) {
// puts("000@@@@@@@@");
// printf("CUT : %d %d\n",x,y);
evert(x);
access(y);
Splay(x);
ch[x][1] = fa[y] = 0;
}
int faa[maxn],atid[maxn],tot;
int getfa(int x) {
return x == faa[x] ? x : faa[x] = getfa(faa[x]);
}
inline void kruskal() {
for(int i=1; i<=3*n; ++i)faa[i] = i;
for(int i=1; i<=m; ++i) {
if(!del[(Shik) {0,e[i].from,e[i].to}]) {
int fx = getfa(e[i].from),fy = getfa(e[i].to);
if(fx == fy)continue;
// printf("Kruskal:%d %d %d %d\n",i,e[i].from,e[i].to,e[i].val);
faa[fx] = fy,++tot;
maxxid[n+tot] = n+tot,val[n+tot] = maxx[n+tot] = e[i].val;
// printf("MSTFinal:%d %d %d %d\n",e[i].from,n+tot,e[i].to,e[i].val);
atid[n+tot] = i;
// printf("atid:%d %d\n",n+tot,i);
link(e[i].from,n+tot),link(n+tot,e[i].to);
// printf("MSTl LINK:%d %d %d\n",e[i].from,e[i].to,n+tot);
if(tot == n-1)return ;
}
}
}
int main() {
// system("fc ans.txt P4172_2.out");
freopen("P4172_2.in","r",stdin);
freopen("ans.txt","w",stdout);
scanf("%d %d %d",&n,&m,&q);
for(int i=1; i<=m; ++i) {
scanf("%d %d %d",&e[i].from,&e[i].to,&e[i].val);
if(e[i].from > e[i].to)swap(e[i].from , e[i].to);
del[(Shik) {0,e[i].from,e[i].to}] = 0;
eval[(Shik) {0,e[i].from,e[i].to}] = e[i].val;
}
std :: sort(e+1,e+m+1);
for(int i=1;i<=m;++i)eid[(Shik) {0,e[i].from,e[i].to}] = i;
for(int i=1; i<=q; ++i) {
scanf("%d %d %d",&op[i].ty,&op[i].x,&op[i].y);
if(op[i].x > op[i].y)swap(op[i].x , op[i].y);
if(op[i].ty == 2)del[(Shik) {0,op[i].x,op[i].y}] = 1;
}
kruskal();
for(int i=q; i; --i) {
if(op[i].ty == 1) {
split(op[i].x,op[i].y);
ans[++anscnt] = maxx[op[i].y];
// printf("ANS : %d %d\n",anscnt,ans[anscnt]);
}
if(op[i].ty == 2) {
split(op[i].x,op[i].y);
int vall = eval[(Shik) {0,op[i].x,op[i].y}],idd = eid[(Shik) {0,op[i].x,op[i].y}];
if(vall >= maxx[op[i].y])continue;
int tempf = e[atid[maxxid[op[i].y]]].from,tempt = e[atid[maxxid[op[i].y]]].to,opy = maxxid[op[i].y];
cut(tempf,opy);
cut(tempt,opy);
val[n+(++tot)] = maxx[n+tot] = vall ,maxxid[n+tot] = n+tot;
atid[n+tot] = idd;
link(op[i].x,n+tot),link(op[i].y,n+tot);
// printf("VALL : %d\n",vall);
// printf("cuts : %d %d %d %d\n",maxxid[op[i].y],e[atid[maxxid[op[i].y]]].from,atid[maxxid[op[i].y]],e[atid[maxxid[op[i].y]]].to);
// printf("links: %d %d %d %d\n",op[i].x,n+(tot+1),op[i].y,n+tot+1);
}
}
for(int i=anscnt; i; --i)printf("%d\n",ans[i]);
return 0;
}
求求大佬救救我