bzoj3510 首都

bzoj3510 首都

​​ 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 HINT 对于100%的数据，2<=N<=100000，1<=M<=200000。 树的中心的定义：使得这个节点所有子树中最大的最小 另：树的中心中的子树最大不会超过n/2 性质1、每次往树上添加一个节点 树的中心只会往那个方向移动1个或者不移动 为什么考虑性质 不超过n/2 因为考虑 之前重心定义所产生的一个不等式 如果不符合性质1 也就违反了前面的定义了 2、树中所有点到某个点的距离总和 一定是中心最小 可以考虑随便取中心附近的一个点 把他们的距离单独算 然后通过算是否走这条边来验证 3、两棵树连接起来 重心一定在路径上 （两点在树上只有唯一路径 如果这个点在其中是重心了 那么在这个子树的其他节点就更不可能了 这题动态维护重心 每次合并的时候启发式合并 复杂度n^(log(n)^2) 合并的时候需要注意几点问题 就是我因为规定了合并的点所以我需要dfs一下要被分拆的树 然后一个一个往自己的父亲连 因为自己的父亲已经在新的树上了.. 连接完之后还要注意维护重心的改变 那么首先先把y的重心找出来 然后将access(x) 那么这时候就在一个splay上了 那么我只需要找一下y的x方向的子树大小有没有超过n/2或者是编号更小 转移下即可 另外此题需要维护虚边的一些信息 那么就参考bzoj beijing大融合那题了 虚点数量的改变只会在access的时候出现问题 需要维护 我在学习了icefox巨佬的做法上尝试自己码的时候稍微优化了下常数 跑的快了一点点

#include#include#define N 110000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while(ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=gc();} while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x*f;}struct node{ int y,next;}data[N<<1];int num,h[N],sizex[N],size[N],c[N][2],fa1[N],fa[N],sizef[N],q[N],top,ans,g[N],n,m;bool rev[N];inline void insert1(int x,int y){ data[++num].y=y;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].next=h[y];h[y]=num;}inline int find(int x){ while(fa1[x]!=x) x=fa1[x]=fa1[fa1[x]];return x;}inline void update(int x){ size[x]=size[c[x][0]]+size[c[x][1]]+sizex[x]+1;}inline void pushdown(int x){ if (!rev[x]) return;rev[x]^=1;rev[c[x][0]]^=1; rev[c[x][1]]^=1;swap(c[x][0],c[x][1]);}inline bool isroot(int x){ return c[fa[x]][0]!=x&&c[fa[x]][1]!=x;}inline void rotate(int x){ int y=fa[x],z=fa[y],l=c[y][1]==x,r=l^1; if (!isroot(y)) c[z][c[z][1]==y]=x; fa[c[x][r]]=y;fa[y]=x;fa[x]=z; c[y][l]=c[x][r];c[x][r]=y;update(y);update(x);}inline void splay(int x){ q[top=1]=x;for (int i=x;!isroot(i);i=fa[i]) q[++top]=fa[i]; while(top) pushdown(q[top--]); while(!isroot(x)){ int y=fa[x],z=fa[y]; if (!isroot(y)){ if (c[y][0]==x^c[z][0]==y) rotate(x);else rotate(y); }rotate(x); }}inline void access(int x){ for (int t=0;x;t=x,x=fa[x]) splay(x),sizex[x]+=size[c[x][1]]-size[t],c[x][1]=t,update(x);}inline void makeroot(int x){ access(x);splay(x);rev[x]^=1;}inline void print(int x){ if (c[x][0]) print(c[x][0]); printf("%d,x); if (c[x][1]) print(c[x][1]);} inline void link(int x,int y){ makeroot(y);fa[x]=y;sizex[y]+=size[x];update(y); int root=g[find(y)];makeroot(root);access(x);splay(root); int xx=c[root][1],sz=size[root];pushdown(xx); while(c[xx][0]) xx=c[xx][0],pushdown(xx);splay(xx);int sz1=size[xx]-size[c[xx][0]]; if ((sz1<<1)>sz||xxsizef[yy]) swap(xx,yy),swap(x,y); fa1[xx]=yy;sizef[yy]+=sizef[xx];ans^=g[xx];merge(x,y);insert1(x,y); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。