正题

题目链接:https://www.luogu.com.cn/problem/P2056

---

题目大意

$n$个点的一棵树，开始全是黑点，有操作

取反一个点的颜色

求最远的黑点之间的距离

---

解题思路

根据点分治每个点和分散开来的重心连边，然后每个点往上只会有$log$层节点。

对于每个点分树上节点我们需要维护最长路和次长路，然后要注意它们不能在同一个点分子树上。

只会对于每个点$x$我们需要维护$x$的点分树子树中每个点到$x$的父节点的真实距离的堆。然后还有每个点的所有子节点的堆顶元素的堆。还有一个维护每个节点答案的堆。

时间复杂度$O(n\log n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #include<cctype> #include<queue> #include<set> #define mp(x,y) make_pair(x,y) using namespace std; const int N=1e5+10,inf=1e9,T=18; struct node{int to,next; }a[N*2]; int read(){int x=0,f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-f;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; } int n,tot,num,root,q,ls[N],f[N],siz[N],d[N],fa[N]; int dep[N],g[N][T+1];bool v[N],vis[N]; struct heap{priority_queue<int> q1,q2;void insert(int x){q1.push(x);}void erase(int x){q2.push(x);}int top(){while(!q2.empty()&&q1.top()==q2.top())q2.pop(),q1.pop();return q1.top();}int top2(){int w=top();erase(w);int ans=top();insert(w);return ans;}int size(){return q1.size()-q2.size();} }q1[N],q2[N],ans; void addl(int x,int y){a[++tot].to=y;a[tot].next=ls[x];ls[x]=tot;return; } void dfs(int x,int fa){dep[x]=dep[fa]+1;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa)continue;g[y][0]=x;dfs(y,x);}return; } int LCA(int x,int y){if(dep[x]>dep[y])swap(x,y);for(int i=T;i>=0;i--)if(dep[g[y][i]]>=dep[x])y=g[y][i];if(x==y)return x;for(int i=T;i>=0;i--)if(g[x][i]!=g[y][i])x=g[x][i],y=g[y][i];return g[x][0]; } int Dis(int x,int y) {return dep[x]+dep[y]-dep[LCA(x,y)]*2;} void groot(int x,int fa){siz[x]=1;f[x]=0;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa||vis[y])continue;groot(y,x);siz[x]+=siz[y];f[x]=max(f[x],siz[y]);}f[x]=max(f[x],num-siz[x]);if(f[x]<f[root])root=x;return; } void calc(int x,int fa,int sav,int root){int dis=Dis(root,x);q1[sav].insert(dis);for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(y==fa||vis[y])continue;calc(y,x,sav,root);}return; } int count(int x) {return q2[x].top()+q2[x].top2();} void build(int x){vis[x]=1;q2[x].insert(0);int S=num;for(int i=ls[x];i;i=a[i].next){int y=a[i].to;if(vis[y])continue;root=0;num=(siz[y]<siz[x])?siz[y]:S-siz[x];groot(y,x);y=root;fa[y]=x;calc(y,x,y,x);q2[x].insert(q1[y].top());build(y);}if(q2[x].size()>1)ans.insert(count(x));return; } int main() {n=read();for(int i=1;i<n;i++){int x=read(),y=read();addl(x,y);addl(y,x);}//读入dfs(1,1);for(int j=1;j<=T;j++)for(int i=1;i<=n;i++)g[i][j]=g[g[i][j-1]][j-1];//预处理求LCA f[0]=inf;num=n;groot(1,1);build(root);num=n;memset(v,0,sizeof(v));scanf("%d",&q);while(q--){char op[3];int x;scanf("%s",op);if(op[0]=='C'){x=read();if(!v[x]){v[x]=1;num--;if(q2[x].size()>1)ans.erase(count(x));q2[x].erase(0);if(q2[x].size()>1)ans.insert(count(x));for(int y=x;fa[y];y=fa[y]){if(q2[fa[y]].size()>1)ans.erase(count(fa[y]));q2[fa[y]].erase(q1[y].top());q1[y].erase(Dis(x,fa[y]));if(q1[y].size())q2[fa[y]].insert(q1[y].top());if(q2[fa[y]].size()>1)ans.insert(count(fa[y]));}}else{v[x]=0;num++;if(q2[x].size()>1)ans.erase(count(x));q2[x].insert(0);if(q2[x].size()>1)ans.insert(count(x));for(int y=x;fa[y];y=fa[y]){if(q2[fa[y]].size()>1)ans.erase(count(fa[y]));if(q1[y].size())q2[fa[y]].erase(q1[y].top());q1[y].insert(Dis(x,fa[y]));q2[fa[y]].insert(q1[y].top());if(q2[fa[y]].size()>1)ans.insert(count(fa[y]));}}}if(op[0]=='G'){if(num<=1)printf("%d\n",num-1);else printf("%d\n",ans.top());}}return 0; }

总结

以上是生活随笔为你收集整理的P2056-[ZJOI2007]捉迷藏【点分树,堆】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。