Description
捉迷藏 Jiajia和Wind是一对恩爱的夫妻，并且他们有很多孩子。某天，Jiajia、Wind和孩子们决定在家里玩
捉迷藏游戏。他们的家很大且构造很奇特，由N个屋子和N-1条双向走廊组成，这N-1条走廊的分布使得任意两个屋
子都互相可达。游戏是这样进行的，孩子们负责躲藏，Jiajia负责找，而Wind负责操纵这N个屋子的灯。在起初的
时候，所有的灯都没有被打开。每一次，孩子们只会躲藏在没有开灯的房间中，但是为了增加刺激性，孩子们会要
求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性，Jiajia希望知道可能的最远的两
个孩子的距离（即最远的两个关灯房间的距离）。 我们将以如下形式定义每一种操作： C(hange) i 改变第i个房
间的照明状态，若原来打开，则关闭；若原来关闭，则打开。 G(ame) 开始一次游戏，查询最远的两个关灯房间的
距离。
Input
第一行包含一个整数N，表示房间的个数，房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b，
表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q，表示操作次数。接着Q行，每行一个操作，如
上文所示。
Output
对于每一个操作Game，输出一个非负整数到hide.out，表示最远的两个关灯房间的距离。若只有一个房间是关
着灯的，输出0；若所有房间的灯都开着，输出-1。
Sample Input
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
7
G
C 1
G
C 2
G
C 1
G
Sample Output
4
3
3
4
HINT
对于100%的数据， N ≤100000, M ≤500000。
括号序列的这个方法real神奇
按照深搜序我进这个之前来一个左括号 出这个的时候来个右括号 那么我们最后把这个括号序列生成出来 中间如果匹配就消去 那么这个括号序列最长的部分就是我想要的答案 因为一个括号匹配了就代表这进去将是一个子树 不可能是简单路径 此外感谢zhx巨佬给予的讲解 要不然是不可能理解这题的orz 那么这个怎么维护 我需要存放七个值 分别代表什么 a,b代表这个序列里右括号和左括号的数量 那么以后就用a,b来代替了dis就是我当前这个序列里最长的是多少 lplus就是左起a+b的最大值rplus是右起a+b的最大值 同理lminus是左起b-a的最大值 rminus是右起a-b的最大值 然后像线段树合并一样 分别讨论一下这个最大值是如何维护的 然后这些值都是怎么更新得到的 并且注意有可能不存在点或者只有一个点那么分别输出-1和0怎么搞 我是每个节点记录个size然后每次都update一下 这就可能造成蒟蒻我常数巨大 还有就是这个位置不是(x-1)*3+2因为这个括号序列匹配不确定..我后来选择记录一个Pos数组来搞定
http://www.shuizilong.com/house/archives/bzoj-1095-zjoi2007hide-捉迷藏/
定义一种对一棵树的括号编码。这种编码方式很直观，所以，这里不给出严格的定义，用以下这棵树为例：
(图片自行脑补。。。）
可以先序遍历后写成：[A[B[E][F[H][I]]][C][D[G]]]
去掉字母后的串：[[[][[][]]][][[]]]
就称为这棵树的括号编码。（这个编码本质上是由深度优先遍历得到的）
考察两个结点，如 E 和 G ，
取出介于它们之间的那段括号编码 ：][[][]]][][[
把匹配的括号去掉，得到：]][[
我们看到 2 个 ] 和 2 个 [，也就是说，在树中，从 E 向上爬 2 步，再向下走 2 步就到了 G。
注意到，题目中需要的信息只有这棵树中点与点的距离，所以，贮存编码中匹配的括号是没有意义的。
因此，对于介于两个节点间的一段括号编码 S，可以用一个二元组 (a, b) 描述它，即这段编码去掉匹配括号后有 a 个 ] 和 b 个 [。
所以，对于两个点 PQ，如果介于某两点 PQ 之间编码 S 可表示为 (a, b)，PQ 之间的距离就是 a+b。
也就是说，题目只需要动态维护：max{a+b | S’(a, b) 是 S 的一个子串，且 S’ 介于两个黑点之间}，
这里 S 是整棵树的括号编码。我们把这个量记为 dis(s)。
现在，如果可以通过左边一半的统计信息和右边一半的统计信息，得到整段编码的统计，这道题就可以用熟悉的线段树解决了。
这需要下面的分析。
考虑对于两段括号编码 S1(a1, b1) 和 S2(a2, b2)，如果它们连接起来形成 S(a, b)。
注意到 S1、S2 相连时又形成了 min{b, c} 对成对的括号，合并后它们会被抵消掉。（？..这里 b, c 应该分别是指 b1 和 a2。。。
所以：
当 a2 < b1 时第一段 [ 就被消完了，两段 ] 连在一起，例如：
] ] [ [ + ] ] ] [ [ = ] ] ] [ [
当 a2 >= b1 时第二段 ] 就被消完了，两段 [ 连在一起，例如：
] ] [ [ [ + ] ] [ [ = ] ] [ [ [ （？..反了？。。。
这样，就得到了一个十分有用的结论：
当 a2 < b1 时，(a,b) = (a1-b1+a2, b2)，
当 a2 >= b1 时，(a,b) = (a1, b1-a2+b2)。
由此，又得到几个简单的推论：
(i) a+b = a1+b2+|a2-b1| = max{(a1-b1)+(a2+b2), (a1+b1)+(b2-a2)}
(ii) a-b = a1-b1+a2-b2
(iii) b-a = b2-a2+b1-a1
由 (i) 式，可以发现，要维护 dis(s)，就必须对子串维护以下四个量：
right_plus：max{a+b | S’(a,b) 是 S 的一个后缀，且 S’ 紧接在一个黑点之后}
right_minus：max{a-b | S’(a,b) 是 S 的一个后缀，且 S’ 紧接在一个黑点之后}
left_plus：max{a+b | S’(a,b) 是 S 的一个前缀，且有一个黑点紧接在 S 之后}
left_minus：max{b-a | S’(a,b) 是 S 的一个前缀，且有一个黑点紧接在 S 之后}
这样，对于 S = S1 + S2，其中 S1(a, b)、S2(c, d)、S(e, f)，就有
(e, f) = b < c ? (a-b+c, d) : (a, b-c+d)
dis(S) = max{dis(S1), left_minus(S2)+right_plus(S1), left_plus(S2)+right_minus(S1), dis(S2)}
那么，增加这四个参数是否就够了呢？
是的，因为：
right_plus(S) = max{right_plus(S1)-c+d, right_minus(S1)+c+d, right_plus(S2)}
right_minus(S) = max{right_minus(S1)+c-d, right_minus(S2)}
left_plus(S) = max{left_plus(S2)-b+a, left_minus(S2)+b+a, left_plus(S1)}
left_minus(S) = max{left_minus(S2)+b-a, left_minus(S1)}
这样一来，就可以用线段树处理编码串了。实际实现的时候，在编码串中加进结点标号会更方便，对于底层结点，如果对应字符是一个括号或者一个白点，那 么right_plus、right_minus、left_plus、left_minus、dis 的值就都是 -maxlongint；如果对应字符是一个黑点，那么 right_plus、right_minus、left_plus、left_minus 都是 0，dis 是 -maxlongint。
现在这个题得到圆满解决，回顾这个过程，可以发现用一个串表达整棵树的信息是关键，这一“压”使得线段树这一强大工具得以利用.. .
———— 以上摘自 NOI08 冬令营论文 《数据结构的提炼与压缩》 by cqx 。。。
以上来自岛娘的blog
#include<cstdio>
#include<algorithm>
#define N 110000
#define inf 0x3f3f3f3f
using 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;char ch=gc();
while(ch<'0'||ch>'9') ch=gc();
while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
return x;
}
struct node{
int y,next;
}data[N<<1];
struct tr{
int left,right,a,b,lminus,rminus,lplus,rplus,dis,size;
}tree[N<<3];
int que[N<<2],h[N],num,tot,root,n,m,pos[N];
inline void dfs(int x,int fa){
que[++num]=2;que[++num]=3;pos[x]=num;
for (int i=h[x];i;i=data[i].next){
int y=data[i].y;if (y==fa) continue;
dfs(y,x);
}que[++num]=1;
}
inline void update(int x){
int l=tree[x].left,r=tree[x].right;bool flag=0;
if (tree[l].b<tree[r].a) flag=1;tree[x].size=tree[l].size+tree[r].size;
if (flag) tree[x].a=tree[l].a-tree[l].b+tree[r].a,tree[x].b=tree[r].b;
else tree[x].a=tree[l].a,tree[x].b=-tree[r].a+tree[l].b+tree[r].b;
tree[x].dis=max(max(tree[l].dis,tree[r].dis),max(tree[l].rminus+tree[r].lplus,tree[l].rplus+tree[r].lminus));
int a=tree[l].a,b=tree[l].b,c=tree[r].a,d=tree[r].b;
tree[x].lminus=max(tree[l].lminus,b-a+tree[r].lminus);
tree[x].rminus=max(tree[r].rminus,c-d+tree[l].rminus);
tree[x].lplus=max(max(tree[l].lplus,a+b+tree[r].lminus),a-b+tree[r].lplus);
tree[x].rplus=max(max(tree[r].rplus,c+d+tree[l].rminus),tree[l].rplus+d-c);
}
inline void build(int &x,int l,int r){
x=++tot;if (l==r){
tree[x].a=tree[x].b=0;
tree[x].lminus=tree[x].lplus=tree[x].rminus=tree[x].rplus=tree[x].dis=-inf;
if (que[l]==1) tree[x].a=1;if (que[l]==2) tree[x].b=1;if (que[l]==3)
tree[x].lminus=tree[x].lplus=tree[x].rminus=tree[x].rplus=tree[x].dis=0,tree[x].size=1;
return;
}int mid=l+r>>1;
build(tree[x].left,l,mid);build(tree[x].right,mid+1,r);update(x);
}
inline void insert1(int x,int l,int r,int p){
if (l==r){
if (tree[x].lminus==-inf)
tree[x].lminus=tree[x].lplus=tree[x].rminus=tree[x].rplus=tree[x].dis=0,tree[x].size=1;
else tree[x].lminus=tree[x].lplus=tree[x].rminus=tree[x].rplus=tree[x].dis=-inf,tree[x].size=0;return;
}int mid=l+r>>1;
if (p<=mid) insert1(tree[x].left,l,mid,p);else insert1(tree[x].right,mid+1,r,p);update(x);
}
int main(){
freopen("bzoj1095.in","r",stdin);
n=read();
for (int i=1;i<n;++i){
int x=read(),y=read();
data[++num].y=y;data[num].next=h[x];h[x]=num;
data[++num].y=x;data[num].next=h[y];h[y]=num;
}num=0;dfs(1,0);build(root,1,num);
m=read();
for (int i=1;i<=m;++i){
char ch=gc();while(ch!='C'&&ch!='G') ch=gc();
if (ch=='C'){
int x=read();insert1(root,1,num,pos[x]);
}else{
//printf("%d\n",tree[root].size);
if (tree[root].size==1) {puts("0");continue;}
if (!tree[root].size) {puts("-1");continue;}
printf("%d\n",tree[root].dis);
}
}
return 0;
}动态点分治 顾名思义 就是动态的.. 假如这题不需要有修改操作 那我是不是一遍朴素的点分就可以搞定了 但是现在存在修改怎么办 动态点分的操作就是我首先一遍点分把所有的重心提早找出 然后针对每一个重心的节点我像线段树一样串联起来 这样最多有log层 并且呢 为了统计 我在每个节点上暴力的使用一个数据结构 堆/multiset 来保证我的复杂度 变成n*(logn)^2的 我开设b[x]表示我x分治的这个区域中 所有子树包括自己到我上一层分治点的距离 维护一个大根堆 c[x]表示我x分治区域的这个子树中的每个点到我x节点的上一个分治节点的距离 那么同样也是维护一个大根堆 即可 这个再开设一个A表示全局的最大值 全局最大值都由什么什么构成 那显然就是每个B里面我去选一个最大和次大组合起来啊 但是堆需要删除操作 所以一个小trick 一个堆打标记一个堆加入 或者直接使用Multiset但是效率上会低一点另外为了优化常数还可以使用rmq的lca
代码有些丑陋 因为multiset的用法和priority_queue的用法我都放在一起了turn_on1&turn_off1是multi set的 bzoj大概十多秒吧 用堆的方法就比较快了 turn_on turn_off是堆来维护的
可以自行选择是使用那个此外求lca的方法也是两种lca1是rmq的方法 lca就是普通的倍增
rmq的lca怎么搞 首先遍历一遍整棵树 然后一进一出针对每条边记录两次 一共获得2*n-1个点 先按照顺序把他们依次填入mn数组 然后记录下在mn数组中对应的位置
（注意开数组的时候二倍 预处理log数组的时候也需要预处理两倍的 然后我利用动态规划的思想去搞
设mn[i][j]表示i起始长度为2^j 表示这一段深度最浅的点是谁那么 询问u,v的时候直接返回这两个区间中深度最小的点是谁 即使可能包括u的子树的节点也无妨 因为深度最浅的一定是他们的lca
#include<set>
#include<queue>
#include<cstdio>
#include<algorithm>
#define N 110000
#define inf 0x3f3f3f3f
using 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;char ch=gc();
while(ch<'0'||ch>'9') ch=gc();
while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc();
return x;
}
multiset<int> a,b[N],c[N];
int h[N],num,n,far[N],fa[N][20],dep[N],root,f[N],size[N],sum,m,cnt,bin[20];
int Log[N<<1],tot,mn[N<<1][20],pos[N],tot1;
bool visit[N],light[N];
struct node{
int y,next;
}data[N<<1];
struct heap{
priority_queue<int> A,B;
void push(int x){A.push(x);}
void erase(int x){B.push(x);}
void pop(){
while(B.size()&&A.top()==B.top()) A.pop(),B.pop();A.pop();
}int top(){
while(B.size()&&A.top()==B.top()) A.pop(),B.pop();
if(!A.size()) return 0;return A.top();
}int size(){return A.size()-B.size();}
int stop(){
if(size()<2) return 0;
int x=top();pop();
int y=top();push(x);return y;
}
}B[N],C[N],A;
inline void dfs(int x){
mn[++tot1][0]=x;pos[x]=tot1;
for (int i=h[x];i;i=data[i].next){
int y=data[i].y;if (fa[x][0]==y) continue;fa[y][0]=x;
dep[y]=dep[x]+1;for (int j=1;j<=Log[dep[y]];++j) fa[y][j]=fa[fa[y][j-1]][j-1];
dfs(y);mn[++tot1][0]=x;
}
}
inline void init(){
int t=Log[tot1];
for (int j=1;j<=t;++j)
for (int i=1;i<=tot1;++i){
if(i+bin[j-1]>tot1) break;
if(dep[mn[i][j-1]]<dep[mn[i+bin[j-1]][j-1]])
mn[i][j]=mn[i][j-1];else mn[i][j]=mn[i+bin[j-1]][j-1];
}
}
inline void get_root(int x,int father){
f[x]=0;size[x]=1;
for (int i=h[x];i;i=data[i].next){
int y=data[i].y;if (y==father||visit[y]) continue;
get_root(y,x);size[x]+=size[y];f[x]=max(f[x],size[y]);
}f[x]=max(f[x],sum-size[x]);if (f[root]>f[x]) root=x;
}
inline void solve1(int x,int father){
far[x]=father;visit[x]=1;int sum1=sum;
for (int i=h[x];i;i=data[i].next){
int y=data[i].y;if (visit[y]) continue;
root=0;if (size[y]>size[x]) sum=sum1-size[x];else sum=size[y];
get_root(y,x);solve1(root,x);
}
}
inline int lca(int x,int y){
if (dep[x]<dep[y]) swap(x,y);int dis=dep[x]-dep[y];
for (int i=0;i<=Log[dis];++i) if (bin[i]&dis) x=fa[x][i];
if (x==y) return x;
for (int i=Log[dep[x]];~i;--i)
if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
inline int lca1(int x,int y){
int l=pos[x],r=pos[y];if (l>r) swap(l,r);
int t=Log[r-l+1];
return dep[mn[l][t]]<dep[mn[r-bin[t]+1][t]]?mn[l][t]:mn[r-bin[t]+1][t];
}
inline int dis(int x,int y){
// printf("%d\n",lca(x,y));
return dep[x]+dep[y]-(dep[lca1(x,y)]<<1);
}
inline int c_top(int x){
multiset<int>::iterator ii;
if(c[x].empty()) return 0;
ii=c[x].end();--ii;return *ii;
}
inline int b_top(int x){
multiset<int>::iterator ii;
if(b[x].empty()) return 0;
ii=b[x].end();--ii;return *ii;
}
inline int b_stop(int x){
multiset<int>::iterator ii;
if(b[x].size()<2) return 0;
ii=b[x].end();--ii;--ii;return *ii;
}
inline void turn_on1(int x,int v){
if (x==v){
b[x].insert(0);
if (b[x].size()==2) a.insert(b_top(x));
}if(!far[x]) return;int y=far[x],D=dis(y,v);
int tmp=c_top(x);c[x].insert(D);
if (D>tmp){
int max1=b_top(y)+b_stop(y),sz=b[y].size();
if (tmp)b[y].erase(b[y].find(tmp));b[y].insert(D);
int now=b_top(y)+b_stop(y);
if (now>max1){
if (sz>=2) a.erase(a.find(max1));
if (b[y].size()>=2) a.insert(now);
}
}turn_on1(y,v);
}
inline void turn_on(int x,int v){
if (x==v){
B[x].push(0);//把x点改成黑点
if (B[x].size()==2) A.push(B[x].top());//如果添加上自己正好有两个黑点那么就可以对全局答案产生贡献
}if (!far[x]) return;int y=far[x],D=dis(y,v);//算出被改点到x's father的距离
int tmp=C[x].top();C[x].push(D);//取出最大值 然后将新的距离放入
if (D>tmp){//当x子树到y的最大深度变化了 需要更改B[Y]的值
int max1=B[y].top()+B[y].stop(),sz=B[y].size();
if (tmp) B[y].erase(tmp);B[y].push(D);
int now=B[y].top()+B[y].stop();
if (now>max1){//这时 过Y的合法路径出现了不同 需要去全局修改
if (sz>=2) A.erase(max1);
if (B[y].size()>=2) A.push(now);
}
}turn_on(y,v);
}
inline void turn_off1(int x,int v){
if (x==v){
b[x].erase(b[x].find(0));
if (b[x].size()==1) a.erase(a.find(b_top(x)));
}if (!far[x]) return;int y=far[x],D=dis(y,v);
int tmp=c_top(x);c[x].erase(c[x].find(D));
if (D==tmp){
int max1=b_top(y)+b_stop(y),sz=b[y].size();
b[y].erase(b[y].find(tmp));
if (c_top(x)) b[y].insert(c_top(x));
int now=b_top(y)+b_stop(y);
if (now<max1){
if (sz>=2) a.erase(a.find(max1));
if (b[y].size()>=2) a.insert(now);
}
}turn_off1(y,v);
}
inline void turn_off(int x,int v){
if (x==v){
B[x].erase(0);
if (B[x].size()==1) A.erase(B[x].top());
}if (!far[x]) return;int y=far[x],D=dis(y,v);
int tmp=C[x].top();C[x].erase(D);
if (D==tmp){
int max1=B[y].top()+B[y].stop(),sz=B[y].size();
B[y].erase(tmp);if (C[x].top()) B[y].push(C[x].top());
int now=B[y].top()+B[y].stop();
if (now<max1){
if(sz>=2) A.erase(max1);
if (B[y].size()>=2) A.push(now);
}
}turn_off(y,v);
}
int main(){
freopen("bzoj1095.in","r",stdin);
// freopen("bzoj1095.out","w",stdout);
n=read();for (int i=0;i<=18;++i) bin[i]=1<<i;Log[0]=-1;
for (int i=1;i<=n*2;++i) Log[i]=Log[i>>1]+1;
for (int i=1;i<=n;++i) light[i]=1;cnt=n;
for (int i=1;i<n;++i){
int x=read(),y=read();
data[++num].y=y;data[num].next=h[x];h[x]=num;
data[++num].y=x;data[num].next=h[y];h[y]=num;
}m=read();dfs(1);f[0]=inf;root=0;sum=n;get_root(1,0);solve1(root,0);
init();for (int i=1;i<=n;++i) turn_on(i,i);
for (int i=1;i<=m;++i){
char ch=gc();while(ch!='C'&&ch!='G') ch=gc();
if (ch=='C'){
int x=read();if (light[x]) turn_off(x,x),--cnt;else turn_on(x,x),++cnt;light[x]^=1;
}else if (cnt<2) printf("%d\n",cnt-1);else {
//multiset<int>::iterator ii=a.end();--ii;printf("%d\n",*ii);
printf("%d\n",A.top());
}
}
return 0;
}一开始lca倍增写的有问题 找错足足找了很久orz菜死 然后想办法 怎么去生成一个树然后翻了很久终于找到一个可用的代码 可以生成一棵树 用的是prufer编码 如何生成一棵树 即树的数据生成器
怎么搞 首先先随机一个prufer含有n-2个元素 然后再生成一个集合1~n那么每次我去找一下最小的那个没有在prufer序列中出现的数 把他们连起来 然后在prufer序列中删掉他们重复以上步骤 然后再把最后的两个点连起来即可 对于代码中的做法 就是首先我给每个点度为1 然后随机一个prufer序列把序列里的点的度都+1 然后先按照度排序找到第一个不为0的点 输出prufer序列中的值和我的编号 然后把我的度-1 prufer序列中那个数也-1 程序中我现在固定枚举prufer编码了那么我肯定需要找啊一个不存在这里的数和当前的prufer编码连接 然后把这个删掉 原数列中的度也-1说明现在可以出现在prufer编码中了 因为原来的已经被我删掉了 这个非0就是为了防止重复利用
#include<cstdio>
#include<iostream>
#include<ctime>
#include<cstdlib>
#include<algorithm>
using namespace std;
int a[30000+20];
struct nod
{
int id,d;
}d[30000+20];
bool cmpid(nod x,nod y)//按编号排序
{
return x.id<y.id;
}
bool cmp(nod x,nod y)//按度数排序
{
if(x.d!=y.d)return x.d<y.d;
else return x.id<y.id;
}
int main()
{
freopen("bzoj1095.in","w",stdout);
srand(time(NULL));
int n=rand()%100+1;
cout<<n<<endl;
for(int i=1;i<=n;i++)
{
d[i].d=1;
d[i].id=i;
}
for(int i=1;i<=n-2;i++)a[i]=rand()%n+1;//生成purfer编码
for(int i=1;i<=n-2;i++)d[a[i]].d++;//累加度数
for(int i=1;i<=n-2;i++)
{
sort(d+1,d+n+1,cmp);
int j;
for(j=1;j<=n;j++)if(d[j].d)break;
printf("%d %d\n",d[j].id,a[i]);
d[j].d--;
sort(d+1,d+n+1,cmpid);
d[a[i]].d--;
} //模拟上述过程，找度数为1且编号最小的和purfer编码中当前位
sort(d+1,d+n+1,cmp);
printf("%d %d\n",d[n-1].id,d[n].id);//最后两个点之间连边
/*for(int i=1;i<=n;i++)
{
printf("%d ",(rand()%20)-10);
}*/
int m=rand()%200+1;
cout<<endl;
cout<<m<<endl;
for(int i=1;i<=m;i++)
{
int s=rand()%2;
if (s&1)puts("G");else printf("C %d\n",rand()%n+1);
/*if(s==3)printf("CHANGE "); int a=rand()%n+1; int b=rand()%a+1; while(a==b) { a=rand()%n+1; b=rand()%a+1; } cout<<a<<" "<<b<<endl;*/
}
return 0;
}