为了方便可以用一个数组指针来代替传参.
在处理回答的时候要多注意,如果删不掉一条边记得加上,%%%Nacly_Fish提供的数据
#include<bits/stdc++.h> using namespace std; const int N=10010; #define mod 51061 struct node{ int son[2],fa,val,mmax,t; bool swp; }now[10][N]; node *s; int n,m,C,q; #define ls s[x].son[0] #define rs s[x].son[1] bool isrt(int x){return s[s[x].fa].son[0]!=x && s[s[x].fa].son[1]!=x;} void upd(int x){s[x].mmax=max(s[ls].mmax,max(s[rs].mmax,s[x].val));} void psd(int x){ if(s[x].swp){ s[x].swp^=1;s[ls].swp^=1;s[rs].swp^=1; swap(s[ls].son[0],s[ls].son[1]); swap(s[rs].son[0],s[rs].son[1]); } } void rotate(int x){ int f=s[x].fa,ff=s[f].fa; bool w=s[f].son[1]==x; if(!isrt(f)) s[ff].son[s[ff].son[1]==f]=x;s[x].fa=ff; s[f].son[w]=s[x].son[w^1];s[s[x].son[w^1]].fa=f; s[f].fa=x;s[x].son[w^1]=f; upd(f);upd(x); } void dfs(int x){if(!isrt(x)) dfs(s[x].fa);psd(x);} void splay(int x){ dfs(x); while(!isrt(x)){ int f=s[x].fa,ff=s[f].fa; if(!isrt(f)) s[ff].son[1]==f^s[f].son[1]==x?rotate(x):rotate(f); rotate(x); } } void acs(int x){for(int las=0;x;las=x,x=s[x].fa) splay(x),s[x].son[1]=las,upd(x);} int findrt(int x){acs(x);splay(x);while(s[x].son[0]) psd(x),x=s[x].son[0];splay(x);return x;} void mkrt(int x){acs(x);splay(x);s[x].swp^=1;swap(ls,rs);} void split(int x,int y){mkrt(x);acs(y);splay(y);} int link(int x,int y){ if(s[x].t>=2 || s[y].t>=2) return 1; mkrt(x); if(findrt(y)==x) return 2; s[x].fa=y;s[x].t++;s[y].t++; return 3; } void solve(int x,int y){mkrt(x);printf("%d\n",findrt(y)==x?s[x].mmax:-1);} void relink(int x,int y,int c){ int tf=-1; for(int i=0;i<C;i++){ s=now[i];mkrt(x); if(findrt(y)==x){ splay(y); if(s[y].son[0]!=x || s[x].son[1]) continue; s[x].fa=s[y].son[0]=0;upd(y);tf=i; s[x].t--;s[y].t--; break; } } if(tf==-1) printf("No such edge.\n"); else{ s=now[c]; int k=link(x,y); if(k<=2) printf("Error %d.\n",k),s=now[tf],link(x,y); else printf("Success.\n"); } } void chg(int x,int y){acs(x);splay(x);s[x].val=y;upd(x);} int main(){ scanf("%d %d %d %d",&n,&m,&C,&q); int x,y,c; for(int i=1;i<=n;i++){ scanf("%d",&x); for(int j=0;j<C;j++) now[j][i].val=now[j][i].mmax=x; } for(int i=1;i<=m;i++) scanf("%d %d %d",&x,&y,&c),s=now[c],link(x,y); char ch[10]; while(q--){ scanf("%s %d %d",ch,&x,&y); if(ch[0]=='0') for(int j=0;j<C;j++) s=now[j],chg(x,y); else if(ch[0]=='1') scanf("%d",&c),relink(x,y,c); else scanf("%d",&c),s=now[x],solve(y,c); } }
