解题：WC 2006 水管局长-白红宇

解题：WC 2006 水管局长

阅读量：4460 次

发布时间：2019-06-08

本文共 2687 字，大约阅读时间需要 8 分钟。

初见LCT，动态最小生成树+链上查询max，具体做法是把边转换成点(LCT只能维护点)

时光倒流，先把最后剩的连起来。然后查询就看链上最大值，修改看看链上最大值是否大于当前边，如果是就断开原来的改成当前边

1 #include  2 #include
       
          3 #include
        
           4 #include
         
            5 using namespace std;  6 const int N=110005;  7 struct a{
    int x,y,c;}mst[N];  8 struct b{
    int x,y,typ;}qry[N];  9 map
          
           
            ,int> mmp; 10 int fth[N],son[N][2],val[N]; 11 int maxx[N],stk[N],outp[N]; 12 bool brk[N],rev[N]; 13 int n,m,T,p,t1,t2,cnt,top; 14 bool cmp(a xx,a yy) 15 { 16 return xx.c
            
             mst[mx].c) mx=mx1; if(mst[mx2].c>mst[mx].c) mx=mx2; 23 } 24 void Release(int nde) 25 { 26 if(rev[nde]) 27 { 28 int &lson=son[nde][0],&rson=son[nde][1]; 29 rev[lson]^=1,rev[rson]^=1,rev[nde]^=1; 30 swap(lson,rson); 31 } 32 } 33 bool Nottop(int nde) 34 { 35 int fa=fth[nde]; 36 return son[fa][0]==nde||son[fa][1]==nde; 37 } 38 void Rotate(int nde) 39 { 40 int fa=fth[nde],gr=fth[fa],isl=nde==son[fa][0]; 41 if(Nottop(fa)) son[gr][son[gr][1]==fa]=nde; 42 fth[nde]=gr,fth[fa]=nde,fth[son[nde][isl]]=fa; 43 son[fa][isl^1]=son[nde][isl],son[nde][isl]=fa; 44 Pushup(fa),Pushup(nde); 45 } 46 void Splay(int nde) 47 { 48 stk[top=1]=nde; 49 for(int i=nde;Nottop(i);i=fth[i]) 50 stk[++top]=fth[i]; 51 while(top) Release(stk[top--]); 52 while(Nottop(nde)) 53 { 54 int fa=fth[nde],gr=fth[fa]; 55 if(Nottop(fa)) 56 Rotate(((son[fa][0]==nde)==(son[gr][0]==fa))?fa:nde); 57 Rotate(nde); 58 } 59 } 60 void Access(int nde) 61 { 62 int lst=0,mem=nde; 63 while(nde) 64 { 65 Splay(nde),son[nde][1]=lst; 66 Pushup(nde),lst=nde,nde=fth[nde]; 67 } 68 Splay(mem); 69 } 70 void Turnroot(int nde) 71 { 72 Access(nde),rev[nde]^=1; 73 } 74 int Getroot(int nde) 75 { 76 Access(nde); 77 while(son[nde][0]) 78 nde=son[nde][0]; 79 return nde; 80 } 81 void Split(int x,int y) 82 { 83 Turnroot(x),Access(y); 84 } 85 int Query(int x,int y) 86 { 87 Split(x,y); 88 return maxx[y]; 89 } 90 void Link(int x,int y) 91 { 92 Turnroot(x); 93 if(Getroot(y)!=x) fth[x]=y; 94 } 95 void Cut(int x,int y) 96 { 97 Turnroot(x); 98 if(Getroot(y)==x&&fth[x]==y&&!son[x][1]) 99 son[y][0]=fth[x]=0;100 }101 int main()102 {103 scanf("%d%d%d",&n,&m,&T);104 for(int i=1;i<=m;i++)105 {106 scanf("%d%d%d",&t1,&t2,&mst[i].c);107 if(t1>t2) swap(t1,t2); mst[i].x=t1,mst[i].y=t2;108 }109 sort(mst+1,mst+1+m,cmp);110 for(int i=1;i<=m;i++)111 mmp[make_pair(mst[i].x,mst[i].y)]=i;112 for(int i=1;i<=T;i++)113 {114 scanf("%d%d%d",&qry[i].typ,&t1,&t2);115 if(t1>t2) swap(t1,t2); qry[i].x=t1,qry[i].y=t2;116 if(qry[i].typ==2) brk[mmp[make_pair(t1,t2)]]=true;117 }118 for(int i=1;i<=m;i++)119 val[i+n]=maxx[i+n]=i;120 for(int i=1;i<=m&&cnt