[ZJOI2007]Hide 捉迷藏

2021年09月15日 阅读数:3
这篇文章主要向大家介绍[ZJOI2007]Hide 捉迷藏,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

Description

  捉迷藏 Jiajia和Wind是一对恩爱的夫妻,而且他们有不少孩子。某天,Jiajia、Wind和孩子们决定在家里玩
捉迷藏游戏。他们的家很大且构造很奇特,由N个屋子和N-1条双向走廊组成,这N-1条走廊的分布使得任意两个屋
子都互相可达。游戏是这样进行的,孩子们负责躲藏,Jiajia负责找,而Wind负责操纵这N个屋子的灯。在起初的
时候,全部的灯都没有被打开。每一次,孩子们只会躲藏在没有开灯的房间中,可是为了增长刺激性,孩子们会要
求打开某个房间的电灯或者关闭某个房间的电灯。为了评估某一次游戏的复杂性,Jiajia但愿知道可能的最远的两
个孩子的距离(即最远的两个关灯房间的距离)。 咱们将以以下形式定义每一种操做: C(hange) i 改变第i个房
间的照明状态,若原来打开,则关闭;若原来关闭,则打开。 G(ame) 开始一次游戏,查询最远的两个关灯房间的
距离。ios

Input

  第一行包含一个整数N,表示房间的个数,房间将被编号为1,2,3…N的整数。接下来N-1行每行两个整数a, b,
表示房间a与房间b之间有一条走廊相连。接下来一行包含一个整数Q,表示操做次数。接着Q行,每行一个操做,如
上文所示。ide

Output

  对于每个操做Game,输出一个非负整数到hide.out,表示最远的两个关灯房间的距离。若只有一个房间是关
着灯的,输出0;若全部房间的灯都开着,输出-1。spa

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。游戏

动态点分治ip

它的主要思想就是经过将的重心相连来维护一棵“点分树”,经过“点分树”中各个节点与其儿子间的联系来实如今线修改和查询的目的。ci

这样修改一个点只要顺着父亲跳并更新,显然点分树深度不超过lognget

通过一个点的答案显然是一个子树最远的黑点+另外一个子树最远的黑点string

能够令q1[x]堆表示点到x的上一个根的距离it

这样q2[pa]堆维护pa的子树中的最大距离,q2[pa].push(q1[x].top())io

q3堆表示答案,用q2[x]中的最大值和次大值和插入

不过q2[x]要插入0,以避免出现路径没有超过x的状况没有统计

修改的话:开灯操做就是把q2[x]堆中的0删掉,由于路径不能在x停下

而后从下往上更新,把q1[i]堆中与x到fa[i]的距离删掉

每一步都要从新计算q2,q3

关灯同理,加入0,把距离加入

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<algorithm>
  6 #include<queue>
  7 using namespace std;
  8 const int N=100000;
  9 struct Node
 10 {
 11   int next,to;
 12 }edge[2*N+5];
 13 int head[N+5],num,fa[N+5][21],dep[N+5],size[N+5],maxsize[N+5],minsize,root,FA[N+5],n,m,cnt;
 14 int light[N+5];
 15 char ch[41];
 16 bool vis[N+5];
 17 struct Heap
 18 {
 19   priority_queue<int>q,p;
 20   void push(int x)
 21   {q.push(x);}
 22   void erase(int x)
 23   {p.push(x);}
 24   int top()
 25   {
 26     while (!q.empty()&&!p.empty()&&q.top()==p.top()) q.pop(),p.pop();
 27     return q.top();
 28   }
 29   int sec()
 30   {
 31     while (!q.empty()&&!p.empty()&&q.top()==p.top()) q.pop(),p.pop();
 32     int tmp=q.top();q.pop();
 33     while (!q.empty()&&!p.empty()&&q.top()==p.top()) q.pop(),p.pop();
 34     int val=q.top();
 35     q.push(tmp);
 36     return val;
 37   }
 38   int size()
 39   {
 40     return q.size()-p.size();
 41   }
 42 }q1[100001],q2[100001],q3;
 43 void add(int u,int v)
 44 {
 45   num++;
 46   edge[num].next=head[u];
 47   head[u]=num;
 48   edge[num].to=v;
 49 }
 50 void dfs(int x,int pa)
 51 {int i;
 52   fa[x][0]=pa;
 53   dep[x]=dep[pa]+1;
 54   for (i=head[x];i;i=edge[i].next)
 55     {
 56       int v=edge[i].to;
 57       if (v==pa) continue;
 58       dfs(v,x);
 59     }
 60 }
 61 int lca(int x,int y)
 62 {int i;
 63   if (dep[x]<dep[y]) swap(x,y);
 64   for (i=20;i>=0;i--)
 65     if (dep[x]-(1<<i)>=dep[y]) x=fa[x][i];
 66   if (x==y) return x;
 67   for (i=20;i>=0;i--)
 68     if (fa[x][i]!=fa[y][i])
 69       {
 70     x=fa[x][i];
 71     y=fa[y][i];
 72       }
 73   return fa[x][0];
 74 }
 75 void get_size(int x,int pa)
 76 {int i;
 77   size[x]=1;
 78   maxsize[x]=0;
 79   for (i=head[x];i;i=edge[i].next)
 80     {
 81       int v=edge[i].to;
 82       if (vis[v]||v==pa) continue;
 83       get_size(v,x);
 84       size[x]+=size[v];
 85       if (maxsize[x]<size[v]) maxsize[x]=size[v]; 
 86     }
 87 }
 88 void get_root(int x,int r,int pa)
 89 {int i;
 90   maxsize[x]=max(maxsize[x],size[r]-size[x]);
 91   if (minsize>maxsize[x])
 92     {
 93       minsize=maxsize[x];
 94       root=x;
 95     }
 96   for (i=head[x];i;i=edge[i].next)
 97     {
 98       int v=edge[i].to;
 99       if (v==pa||vis[v]) continue;
100       get_root(v,r,x);
101     }
102 }
103 int dist(int x,int y)
104 {
105   int z=lca(x,y);
106   return dep[x]+dep[y]-2*dep[z];
107 }
108 void get_dist(int x,int pa,int fa)
109 {int i;
110   q1[root].push(dist(pa,x));
111   for (i=head[x];i;i=edge[i].next)
112     {
113       int v=edge[i].to;
114       if (v==fa||vis[v]) continue;
115       get_dist(v,pa,x);
116     }
117 }
118 void work(int x,int pa)
119 {int i;
120   minsize=2e9;
121   get_size(x,0);get_root(x,x,0);
122   FA[root]=pa;vis[root]=1;
123   q2[root].push(0);q1[root].push(dist(root,pa));
124   for (i=head[root];i;i=edge[i].next)
125     {
126       int v=edge[i].to;
127       if (vis[v]) continue;
128       get_dist(v,pa,root);
129     }
130   q2[pa].push(q1[root].top());
131   int rt=root;
132   for (i=head[root];i;i=edge[i].next)
133     {
134       int v=edge[i].to;
135       if (vis[v]) continue;
136       work(v,rt);    
137     }
138   if (q2[rt].size()>=2)
139     q3.push(q2[rt].top()+q2[rt].sec());
140 }
141 void trunon(int x)
142 {int i;
143   if (q2[x].size()>=2)
144     q3.erase(q2[x].top()+q2[x].sec());
145   q2[x].erase(0);
146   if (q2[x].size()>=2)
147     q3.push(q2[x].top()+q2[x].sec());
148   for (i=x;FA[i];i=FA[i])
149     {
150       if (q2[FA[i]].size()>=2) q3.erase(q2[FA[i]].top()+q2[FA[i]].sec());
151       if (q1[i].size()) q2[FA[i]].erase(q1[i].top());
152       q1[i].erase(dist(x,FA[i]));
153       if (q1[i].size()) q2[FA[i]].push(q1[i].top());
154       if (q2[FA[i]].size()>=2) q3.push(q2[FA[i]].top()+q2[FA[i]].sec());
155     }
156 }
157 void trunoff(int x)
158 {int i;
159     if (q2[x].size()>=2)
160     q3.erase(q2[x].top()+q2[x].sec());
161     q2[x].push(0);
162     if (q2[x].size()>=2)
163     q3.push(q2[x].top()+q2[x].sec());
164     for (i=x;FA[i];i=FA[i])
165       {
166     if (q2[FA[i]].size()>=2) q3.erase(q2[FA[i]].top()+q2[FA[i]].sec());
167     if (q1[i].size()) q2[FA[i]].erase(q1[i].top());
168     q1[i].push(dist(x,FA[i]));
169     if (q1[i].size()) q2[FA[i]].push(q1[i].top());
170     if (q2[FA[i]].size()>=2) q3.push(q2[FA[i]].top()+q2[FA[i]].sec());
171       }
172 }
173 int main()
174 {int i,u,v,j,x;
175   cin>>n;
176   for (i=1;i<=n-1;i++)
177     {
178       scanf("%d%d",&u,&v);
179       add(u,v);add(v,u);
180     }
181   cin>>m;
182   dfs(1,0);
183   for (i=1;i<=20;i++)
184     {
185       for (j=1;j<=n;j++)
186     fa[j][i]=fa[fa[j][i-1]][i-1];
187     }
188   work(1,0);
189   cnt=n;
190   for (i=1;i<=m;i++)
191     {
192       scanf("%s",ch);
193       if (ch[0]=='G')
194     {
195       if (cnt<=1) printf("%d\n",cnt-1);
196       else printf("%d\n",q3.top());
197     }
198       else
199     {
200       scanf("%d",&x);
201       if (light[x]==0) trunon(x),cnt--;
202       else trunoff(x),cnt++;
203       light[x]^=1;
204     }
205     }
206 }