BZOJ3510首都（LCT）

Description

在X星球上有N个国家，每个国家占据着X星球的一座城市。由于国家之间是敌对关系，所以不同国家的两个城市是不会有公路相连的。
X星球上战乱频发，如果A国打败了B国，那么B国将永远从这个星球消失，而B国的国土也将归A国管辖。A国国王为了加强统治，会在A国和B国之间修建一条公路，即选择原A国的某个城市和B国某个城市，修建一条连接这两座城市的公路。
同样为了便于统治自己的国家，国家的首都会选在某个使得其他城市到它距离之和最小的城市，这里的距离是指需要经过公路的条数，如果有多个这样的城市，编号最小的将成为首都。
现在告诉你发生在X星球的战事，需要你处理一些关于国家首都的信息，具体地，有如下3种信息需要处理：
1、A x y：表示某两个国家发生战乱，战胜国选择了x城市和y城市，在它们之间修建公路（保证其中城市一个在战胜国另一个在战败国）。
2、Q x：询问当前编号为x的城市所在国家的首都。
3、Xor：询问当前所有国家首都编号的异或和。

Input

第一行是整数N，M，表示城市数和需要处理的信息数。
接下来每行是一个信息，格式如题目描述（A、Q、Xor中的某一种）。

Output

输出包含若干行，为处理Q和Xor信息的结果。

Sample Input

10 10
Xor
Q 1
A 10 1
A 1 4
Q 4
Q 10
A 7 6
Xor
Q 7
Xor

Sample Output

11
1
1
1
2
6
2

解题思路：

主要是动态维护重心。

可以证明，新的中心在原来两个树中心路径上。

那么就把这段路径提取出来找就好了。

注意将重心旋转至根，保证时间复杂度。

代码：

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 #define lll tr[spc].ch[0]
  5 #define rrr tr[spc].ch[1]
  6 #define ls ch[0]
  7 #define rs ch[1]
  8 struct trnt{
  9     int ch[2];
 10     int fa;
 11     int lzt;
 12     int wgt;
 13     int wgti;
 14     int ff;
 15     bool anc;
 16 }tr[1000000];
 17 int st[1000000];
 18 int tp;
 19 int n,m;
 20 int Xorsum;
 21 char cmd[10];
 22 bool whc(int spc)
 23 {
 24     return tr[tr[spc].fa].rs==spc;
 25 }
 26 int finf(int x)
 27 {
 28     return tr[x].ff==x?x:tr[x].ff=finf(tr[x].ff);
 29 }
 30 void pushup(int spc)
 31 {
 32     if(!spc)
 33         return ;
 34     tr[spc].wgt=tr[spc].wgti+tr[lll].wgt+tr[rrr].wgt+1;
 35     return ;
 36 }
 37 void trr(int spc)
 38 {
 39     if(!spc)
 40         return;
 41     std::swap(lll,rrr);
 42     tr[spc].lzt^=1;
 43     return ;
 44 }
 45 void pushdown(int spc)
 46 {
 47     if(tr[spc].lzt)
 48     {
 49         trr(lll);
 50         trr(rrr);
 51         tr[spc].lzt=0;
 52     }
 53     return ;
 54 }
 55 void recal(int spc)
 56 {
 57     if(!tr[spc].anc)
 58         recal(tr[spc].fa);
 59     pushdown(spc);
 60     return ;
 61 }
 62 void rotate(int spc)
 63 {
 64     int f=tr[spc].fa;
 65     bool k=whc(spc);
 66     tr[f].ch[k]=tr[spc].ch[!k];
 67     tr[spc].ch[!k]=f;
 68     if(tr[f].anc)
 69     {
 70         tr[spc].anc=1;
 71         tr[f].anc=0;
 72     }else
 73         tr[tr[f].fa].ch[whc(f)]=spc;
 74     tr[spc].fa=tr[f].fa;
 75     tr[f].fa=spc;
 76     tr[tr[f].ch[k]].fa=f;
 77     pushup(f);
 78     pushup(spc);
 79     return ;
 80 }
 81 void splay(int spc)
 82 {
 83     recal(spc);
 84     while(!tr[spc].anc)
 85     {
 86         int f=tr[spc].fa;
 87         if(tr[f].anc)
 88         {
 89             rotate(spc);
 90             break;
 91         }
 92         if(whc(spc)^whc(f))
 93             rotate(spc);
 94         else
 95             rotate(f);
 96         rotate(spc);
 97     }
 98     return ;
 99 }
100 void access(int spc)
101 {
102     int lst=0;
103     while(spc)
104     {
105         splay(spc);
106         tr[spc].wgti+=tr[rrr].wgt;
107         tr[spc].wgti-=tr[lst].wgt;
108         tr[rrr].anc=1;
109         tr[lst].anc=0;
110         rrr=lst;
111         pushup(spc);
112         lst=spc;
113         spc=tr[spc].fa;
114     }
115     return ;
116 }
117 void Mtr(int spc)
118 {
119     access(spc);
120     splay(spc);
121     trr(spc);
122     return ;
123 }
124 void split(int x,int y)
125 {
126     Mtr(x);
127     access(y);
128     splay(y);
129     return ;
130 }
131 void link(int x,int y)
132 {
133     split(x,y);
134     tr[x].fa=y;
135     tr[y].wgti+=tr[x].wgt;
136     pushup(y);
137     return ;
138 }
139 int Gravity(int spc)
140 {
141     int lwgt=0;
142     int rwgt=0;
143     int tot=tr[spc].wgt/2;
144     int odd=tr[spc].wgt&1;
145     int ans=0x3f3f3f3f;
146     while(spc)
147     {
148         pushdown(spc);
149         int ll,rr;
150         ll=lwgt+tr[lll].wgt;
151         rr=rwgt+tr[rrr].wgt;
152         if(ll<=tot&&rr<=tot)
153         {
154             if(odd)
155             {
156                 ans=spc;
157                 break;
158             }
159             if(ans>spc)
160                 ans=spc;
161         }
162         if(ll>rr)
163         {
164             rwgt+=(tr[spc].wgti+tr[rrr].wgt+1);
165             spc=lll;
166         }else{
167             lwgt+=(tr[spc].wgti+tr[lll].wgt+1);
168             spc=rrr;
169         }
170     }
171     splay(ans);
172     return ans;
173 }
174 int main()
175 {
176     scanf("%d%d",&n,&m);
177     for(int i=1;i<=n;i++)
178     {
179         tr[i].wgt=tr[i].anc=1;
180         tr[i].ff=i;
181         Xorsum^=i;
182     }
183     while(m--)
184     {
185         scanf("%s",cmd);
186         if(cmd[0]=='A')
187         {
188             int x,y;
189             scanf("%d%d",&x,&y);
190             link(x,y);
191             x=finf(x);
192             y=finf(y);
193             split(x,y);
194             int g=Gravity(y);
195             Xorsum=Xorsum^x^y^g;
196             tr[x].ff=tr[y].ff=tr[g].ff=g;
197         }
198         if(cmd[0]=='Q')
199         {
200             int x;
201             scanf("%d",&x);
202             printf("%d
",finf(x));
203         }
204         if(cmd[0]=='X')
205         {
206             printf("%d
",Xorsum);
207         }
208     }
209     return 0;
210 }