数据规模
从别的oj网址上找的
对于20%的数据， N ≤50, M≤100；
对于60%的数据， N ≤3000, M ≤10000；
对于100%的数据， N ≤100000, M≤500000。
解题思路
这题我做了两种解法，第一种思路不好想，但是很快，复杂度为O(nlogn)，另一种比较好想（但实际上并不好写），但是复杂度略高，为O(n logn logn)
思路一：括号序列
用到的知识：线段树
括号序列的定义
括号序列是可以理解为把一颗树拍扁，变成一个序列，这样我们就可以用各种数据结构来维护这颗树了
具体的方法如下：
这是一颗树：
我们从根节点开始遍历，每经过一个点，就加入一个"(",每当一个点的子树遍历完，就加入一个")",然后我们就得到了这颗树的括号序列：
(1(2)(3(4)(5)))
关于括号序列的结论
如果我们有了一颗树的括号序列，我们可以得到以下结论：
i,j之间的距离等于i与j之间的失配括号总数。
什么意思？比如我们要找1,5之间的距离，我们列出1，5之间的括号：()(()(,其中有两组括号是匹配的，即有两组"("在")"前面，删去匹配的括号后，还剩下((,两个括号，所有1，5之间的距离为2
为什么有这个结论？因为匹配的括号表示那个点所有的子节点都跑完了，但是没有经过i,j（否则右括号就会在j后面），所以i,j间的距离就是i,j间的失配括号总数
如何产生一颗树的括号序列
按顺序遍历即可，代码实现如下：
void dfs(int u,int fa){
s[++cnt]=-1;//先加入左括号
s[++cnt]=u;//再加入该点
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].v;
if(v==fa)continue;
dfs(v,u);
}
s[++cnt]=-2;//子树跑完了加入右括号
}括号序列怎么用
我们可以将树拍扁成一个序列，然后可以直接用数据结构来维护这颗树，比如说用线段树来维护，对于本题，我们使用线段树来维护区间内最大的两个关灯点的距离
对于一个区间，我们用a,b来表示这个区间的右，左失配括号数量（因为一个区间右括号一定在左括号前面，否则会匹配掉），用val来表示这个区间的失配括号数量之和，所以对于任意两个相邻的区间(不是指线段树的区间，而是任意区间）1,2，有：
val=a1+abs(b1-a2)+b2
a1,a2,b1,b2，表示两个区间的右左括号数
稍微变形一下：
val=va1+abs(b1-a2)+b2=max((a1+b1)+(b2-a2),(a1-b1)+(a2+b2))
即max(左区间的(a+b)+右区间的(b-a),左区间的(a-b)+右区间的(a+b))
接下来引入线段树来维护区间：
对于每一个线段树的区间，如何根据左右子区间来维护val？
我们定义l1,l2,r1,r2来表示最大前缀(a-b),最大前缀(a+b)，最大后缀(a+b),最大后缀(b-a)，这样val=max(max(lson.val,rson.val),max(lson.r1+rson.l1,lson.r2+rson.l2))
接下来是维护l1,l2,r1,r2:
tr[i].l1=max(lson.l1,rson.l1-lson.a+lson.b);//取左边的max或者右边的max与左边整体
tr[i].l2=max(lson.l2,max(rson.l2-lson.b+lson.a,rson.l1+lson.b+lson.a));
//注：rson.l1+lson.b==rson.b+(lson.b-rson.a)
tr[i].r1=max(rson.r1,max(lson.r1-rson.a+rson.b,lson.r2+rson.a+rson.b));
//注：lson.r2+rson.a==lson.a+(rson.a-lson.b)
tr[i].r2=max(rson.r2,lson.r2+rson.a-rson.b);//取右边的max或左边的max与右边整体 比较难理解的是那两个a+b,自己看注释体会一下，还理解不了可以画画图
维护a,b:
if(lson.b>rson.a){
tr[i].a=lson.a;
tr[i].b=lson.b-rson.a+rson.b;//左区间的左括号与右区间的右括号抵消
}
else{
tr[i].a=rson.a-lson.b+lson.a;
tr[i].b=rson.b;
}然后，对于所有线段树内的最底层的点如何定义呢？
如果这个点是左括号，那就b=1,右括号那就a=1
如果这个点是关灯点，那就l1,l2,r1,r2=0
否则l1,l2,r1,r2=-inf，表示所有的非关灯点（包括括号点和开灯点）全部都不参与答案的统计
初始的val为-inf，因为单个点的val没有意义，两个点构成的区间的val必须由l1,l2,r1,r2生成
至此，基本上的难点都已经讲完了，剩下的直接看完整代码就能看懂了
完整代码
//[ZJOI2007]捉迷藏
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
inline int Read(){
int x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
inline char Readc(){
char c=getchar();
while(c!='C'&&c!='G')c=getchar();
return c;
}
const int mx=100100;
const int inf=1<<29;
int n;
struct Edge{
int v;
int next;
}edge[mx<<1];
int top,head[mx];
void addedge(int u,int v){
edge[++top].v=v;
edge[top].next=head[u];
head[u]=top;
}
void add(int u,int v){
addedge(u,v);
addedge(v,u);
}
int s[mx*3];//树形成的括号序列,-1表示左括号，-2表示右括号，u表示点的编号
int cnt;//总的点数
int pos[mx];//每个点对应的线段树内的点的位置
int on[mx];//on[u]:u点是否开灯
void dfs(int u,int fa){
s[++cnt]=-1;//先加入左括号
s[++cnt]=u;//再加入该点
pos[u]=cnt;//记录每个点在线段树内的位置
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].v;
if(v==fa)continue;
dfs(v,u);
}
s[++cnt]=-2;//子树跑完了加入右括号
}
#define lson tr[i<<1]
#define rson tr[i<<1|1]
struct Node{
int a,b,l1,l2,r1,r2,val;
//设a1,a2,b1,b2分别表示左右区间（指任意区间，而非线段树的区间）的右，左括号
//val=max(a1+abs(a2-b1)+b2)=max((a1+b1)+(b2-a2),(a1-b1)+(a2+b2))
//a,b:每个区间的右左括号数
//l1,l2:前缀max(b-a),max(a+b)
//r1,r2:后缀max(a+b),max(a-b)
int l,r;//线段树区间左右端点
}tr[(3*mx)<<2];
inline int max(int x,int y){return x>y?x:y;}
void update(int i){
if(lson.b>rson.a){
tr[i].a=lson.a;
tr[i].b=lson.b-rson.a+rson.b;//左区间的左括号与右区间的右括号抵消
}
else{
tr[i].a=rson.a-lson.b+lson.a;
tr[i].b=rson.b;
}
tr[i].l1=max(lson.l1,rson.l1-lson.a+lson.b);//取左边的max或者右边的max与左边整体
tr[i].l2=max(lson.l2,max(rson.l2-lson.b+lson.a,rson.l1+lson.b+lson.a));
//注：rson.l1+lson.b==rson.b+(lson.b-rson.a)
tr[i].r1=max(rson.r1,max(lson.r1-rson.a+rson.b,lson.r2+rson.a+rson.b));
//注：lson.r2+rson.a==lson.a+(rson.a-lson.b)
tr[i].r2=max(rson.r2,lson.r2+rson.a-rson.b);//取右边的max或左边的max与右边整体
tr[i].val=max(max(lson.val,rson.val),max(lson.r1+rson.l1,lson.r2+rson.l2));
}
void build(int i,int l,int r){
tr[i].l=l,tr[i].r=r;
if(l==r){
tr[i].a=tr[i].b=0;
tr[i].l1=tr[i].l2=tr[i].r1=tr[i].r2=tr[i].val=-inf;
if(s[l]==-1)tr[i].b=1;
else if(s[l]==-2)tr[i].a=1;
else if(on[s[l]]==0)tr[i].l1=tr[i].l2=tr[i].r1=tr[i].r2=0;//将关灯的点改为0
return;
}
int mid=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
update(i);
}
void change(int i,int k){//k表示点对应的线段树的点的位置
if(tr[i].l==tr[i].r){
tr[i].a=tr[i].b=0;
tr[i].l1=tr[i].l2=tr[i].r1=tr[i].r2=on[s[k]]?-inf:0;//将开灯的点改为-inf
tr[i].val=-inf;
return;
}
int mid=(tr[i].l+tr[i].r)>>1;
if(k<=mid)change(i<<1,k);
else change(i<<1|1,k);
update(i);
}
int main(){
// freopen("in.txt","r",stdin);
n=Read();
for(int i=1;i<n;++i){
int u=Read(),v=Read();
add(u,v);
}
dfs(1,0);
build(1,1,cnt);
int num=n;//关灯的房间数
int T=Read();
while(T--){
char c=Readc();
if(c=='C'){
int u=Read();
num+=on[u]==1?1:-1;
on[u]^=1;
change(1,pos[u]);
}
else{
if(num==0)printf("-1\n");
else if(num==1)printf("0\n");
else {
printf("%d\n",tr[1].val);
}
}
}
return 0;
}总结
该方法的复杂度为O(nlogn),复杂度是十分优秀的，但是思维量巨大，尤其是val的变形以及l1,l2,r1,r2的维护，十分难想，如果是考试，多半想不出来或者没时间想
所以，我们有必要学习一下思路二，这是更一般的做法
思路二：点分树
用到的知识：点分树（会点分治就行）+堆
点分树是什么
前置知识：点分治
在点分治中我们找到了每个子树的重心，如果把每一层子树的重心当成上一层重心的儿子节点，我们就构成了一颗树：<stron>，所以，很显然，这颗树的点数为n，层数为logn
有了这样一颗点分树之后，有如下结论：
我们修改一个点时，受到影响的点有：这个点沿点分树一直到根的所有点
所以，每次只需要进行logn次修改就可以修改与这个点有关的所有路径</stron>
为什么想到点分树
对于树上的路径问题，点分治是一个非常常用，且非常高效的算法，而如果题目涉及修改操作，一般就要使用点分树
本题的解法
本题的要求是求最长的路径，我们可以对于每一个重心，维护它每个子节点（下层重心）对应区域的所有点到该点的距离，然后对 每个区域的最长距离 中第一长和第二长的统计答案。
这两个操作我们都可以用堆来实现，即：
对每个点开两个堆fdist,sdist,fdist装该点所在区域内所有点到该点父节点（上一层的重心）的距离，sdist装该点所有子节点（下一层的重心）所对应区域的最长距离（即下层重心的fdist的堆顶），然后将每个点的sdist的堆顶和第二堆顶（堆顶出堆后的堆顶）装入ans堆中
对于每次修改操作，我们需要将特定的距离删除或者入堆，入堆很容易，但是删除怎么实现？
于是，本题所需的数据结构变为：能找出最大元素且能删除特定元素
有两种思路：
1.用平衡树
2.用两个堆，一个为原来的堆，一个为删除堆，对于每次删除操作，我们只需将元素加入删除堆，然后对于每次找堆顶操作，我们需要判断两个堆的堆顶是否相等，如果相等，就同时出堆
我建议用第二种，常数小，且代码短。
完整代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
inline int Read(){
int x=0;
char c=getchar();
while(c>'9'||c<'0')c=getchar();
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return x;
}
inline char Readc(){
char c=getchar();
while(c!='C'&&c!='G')c=getchar();
return c;
}
void write(int x){
if(x>9)write(x/10);
putchar(x%10+'0');
}
const int mx=100100;
int n,m;
struct Edge{
int v;
int next;
}edge[mx<<1];
int top,head[mx];
inline void addedge(int u,int v){
edge[++top].v=v;
edge[top].next=head[u];
head[u]=top;
}
inline void add(int u,int v){
addedge(u,v);
addedge(v,u);
}
inline int max(int x,int y){return x>y?x:y;}
int cnt,c[mx];//关灯的总点数，每个点的状态
int maxn[mx],size[mx],root,s;
int vis[mx];
int fa[mx];//每个点对应点分树上的父亲节点
void find(int u,int f){//找重心
maxn[u]=0,size[u]=1;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].v;
if(v==f||vis[v])continue;
find(v,u);
size[u]+=size[v];
maxn[u]=max(maxn[u],size[v]);
}
maxn[u]=max(maxn[u],s-size[u]);
if(maxn[u]<maxn[root])root=u;
}
int dist[mx][20];//dist[u][deep]表示在deep深度的子树上u到重心的距离,这样定义可以避免每次bfs都memset整个数组
struct Pr_q{
priority_queue<int>q,d;//当前队列，已删除队列
inline void push(int x){q.push(x);}//插入x
inline void del(int x){d.push(x);}//删除x
inline int size(){return q.size()-d.size();}
inline int top(){
while((!q.empty())&&(!d.empty())&&q.top()==d.top()){
q.pop();
d.pop();
}
if(q.empty())return -1e9;
return q.top();
}
inline int two_top(){
if(size()<2)return -1e9;
int tp=top();
q.pop();
int tp2=top();
q.push(tp);
return tp+tp2;
}
}ans,sdist[mx],fdist[mx];//答案堆，所有子节点的最大距离，每个点所在的区域的点到父亲节点的距离
inline void bfs(int s,int deep,int f){//从s出发，在子块内生成每个点到u的距离
queue<int>q;
dist[s][deep]=1;
fdist[f].push(1);
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].v;
if(vis[v])continue;
if(dist[v][deep]==0){
dist[v][deep]=dist[u][deep]+1;
fdist[f].push(dist[v][deep]);
q.push(v);
}
}
}
}
int dep[mx];//每个点的深度
int l_ans[mx];//每个点上次操作后的答案
void solve(int u,int deep){//u:本层的重心,deep:深度
vis[u]=1;
sdist[u].push(0);//这个点与一条子路径构成路径
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].v;
if(vis[v])continue;
maxn[root=0]=1<<30;
s=size[v];
find(v,0);
fa[root]=u;
dep[root]=dep[u]+1;
bfs(v,deep,root);
sdist[u].push(fdist[root].top());
solve(root,deep+1);
}
l_ans[u]=sdist[u].two_top();
ans.push(l_ans[u]);
}
inline void change(int u){//改变u点的状态
c[u]^=1;
if(c[u]==0)++cnt,sdist[u].push(0);
else --cnt,sdist[u].del(0);
int now=u;//从u一直更新到根
while(now){
int now_ans=sdist[now].two_top();
if(l_ans[now]!=now_ans){
ans.del(l_ans[now]);
ans.push(l_ans[now]=now_ans);//修改该点的答案
}
if(fa[now]==0)break;
int x1=fdist[now].top();
if(c[u]==0)fdist[now].push(dist[u][dep[now]-1]);
else fdist[now].del(dist[u][dep[now]-1]); //更新fdist堆
int x2=fdist[now].top();
if(x1!=x2){
sdist[fa[now]].del(x1);
sdist[fa[now]].push(x2);//更新now的父亲的sdist堆
}
now=fa[now];
}
}
int main(){
// freopen("in.txt","r",stdin);
n=Read();
for(int i=1;i<n;++i){
int u=Read(),v=Read();
add(u,v);
}
s=n;
maxn[0]=1<<30;
find(1,0);
dep[root]=0;
solve(root,0);
cnt=n;//关灯的房间数
int T=Read();
while(T){
char c=Readc();
if(c=='G'){
if(cnt==0)printf("-1\n");
else if(cnt==1)printf("0\n");
else {
write(ans.top());
putchar('\n');
}
}
else{
int x=Read();
change(x);
}
--T;
}
return 0;
}总结
虽然代码长，复杂度高（复杂度为O(n logn logn))但是思路却比括号序列简单了不少，已经看懂括号序列的也建议学一下点分树，这种方法适用面更广。另外，由于点分树巨大的常数（或许是我写的太差了），这道题虽然理论复杂度可以过，但实际提交却有一个点T了（别的oj网站上能过，别问，问就是牛客网评测姬太菜了）
京公网安备 11010502036488号