解题：WC 2006 水管局长

初见LCT，动态最小生成树+链上查询max，具体做法是把边转换成点(LCT只能维护点)
时光倒流，先把最后剩的连起来。然后查询就看链上最大值，修改看看链上最大值是否大于当前边，如果是就断开原来的改成当前边
  1 #include<map>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  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<pair<int,int>,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<yy.c;
 17 }
 18 void Pushup(int nde)
 19 {
 20     maxx[nde]=val[nde]; 
 21     int &mx=maxx[nde],&mx1=maxx[son[nde][0]],&mx2=maxx[son[nde][1]];
 22     if(mst[mx1].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<n-1;i++)
121         if(!brk[i])
122         {
123             int tx=mst[i].x,ty=mst[i].y;
124             Turnroot(tx);
125             if(Getroot(ty)!=tx)
126                 cnt++,Link(tx,i+n),Link(ty,i+n);
127         }
128     for(int i=T;i;i--)
129         if(qry[i].typ==1) 
130             outp[++p]=mst[Query(qry[i].x,qry[i].y)].c;
131         else 
132         {
133             int tx=qry[i].x,ty=qry[i].y;
134             int id=mmp[make_pair(tx,ty)],me=Query(tx,ty);
135             if(mst[id].c<mst[me].c)
136             {
137                 Cut(mst[me].x,me+n),Cut(mst[me].y,me+n);
138                 Link(tx,id+n),Link(ty,id+n);
139             }
140         }
141     while(p)
142         printf("%d
",outp[p--]);
143     return 0;
144 }
View Code