括号序列 || 动态树分治 bzoj1095【ZJOI2007】Hide 捉迷藏

本文主要是介绍括号序列 || 动态树分治 bzoj1095【ZJOI2007】Hide 捉迷藏，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：
给出一棵树，初始全是黑点，每次修改把黑点变成白点或把白点变成黑点，每次查询树中黑点最远距离。

题目分析：
两种做法。
第一种：括号序列
这个做法真的比较神啊，无论是代码长度，时间，还是空间都完虐动态树分治。

上边的是动态树分治，下边的是括号序列。
做法大致是把树转化成一个括号序列，然后维护一个线段树。
对于这个神做法，我还是不多BB，大家一起膜岛娘吧 _ (:зゝ∠) _
括号序列做法——岛娘博客传送门

第二种：动态树分治
其实和普通的树分治差不多，就是能够动态修改而已。
我们在树分治的时候每一次都找到一个重心，然后把这颗子树又分成若干棵子树。我们从这个重心向它分出的所有子树的重心连边，作为它的儿子，又形成了一颗新的树。

我们可以发现一些性质，对于新树中的每一个节点，它子树中的所有节点也是原树中它子树中的节点。

所以更改一个节点，只需要改这个节点到根节点路径上的内容。

因为树分治之后形成的新树的层数不超过logn层，所以每次修改的时间复杂度不超过logn。

对于每个节点，我们需要维护它的所有子树中到它最远的黑点。
我们维护三个堆：
堆C：存以自己为根的子树中每个黑点到自己在新树上父亲的距离。
堆B：存每一个子树中离自己最远的黑点的距离（如果自己是黑点，还要加上自己到自己的距离，即0），即新树上所有儿子的堆C得堆顶。
堆A：是一个全局的堆，维护最终的答案。对于每一个节点，都把B中的最大值和次大值的和存进堆A。
A的堆顶即为答案。
时间复杂度O（(n+m)log^2n）

括号序列代码：

#include <cstdio>
#include <cstring>
#define MaxN 100005
#define MaxE 500005
#define ls(c) (c<<1)
#define rs(c) (c<<1|1)
using namespace std;
const int INF=0x3fffffff;
inline int Max(int x,int y) { return x>y?x:y; }
int xl[MaxN*3],pos[MaxN];
bool b[MaxN];
int n,m,top,black;
char s[5];
struct Edge{ int v,nes; }eg[MaxE<<1];
int tot,fir[MaxN];
struct tree
{int C2,C5,M25,L25,R25,L5,R2;void init(int x);
}seg[MaxN*12];
void tree :: init(int x)
{C2=xl[x]==-2;C5=xl[x]==-5;M25=-INF;if(xl[x]>0 && !b[xl[x]]) L25=R25=L5=R2=0;else L25=R25=L5=R2=-INF;
}
void edge(int x,int y)
{tot++;eg[tot].v=y;eg[tot].nes=fir[x];fir[x]=tot;
}
#define edge(x,y) edge(x,y),edge(y,x)
void dfs(int c)
{xl[++top]=-5;xl[++top]=c;pos[c]=top;for(int t=fir[c];t;t=eg[t].nes)if(!pos[eg[t].v]) dfs(eg[t].v);xl[++top]=-2;
}
void push_up(int c)
{int L=ls(c),R=rs(c);seg[c].C2=seg[L].C5>seg[R].C2?seg[L].C2:seg[L].C2+seg[R].C2-seg[L].C5;seg[c].C5=seg[L].C5>seg[R].C2?seg[R].C5+seg[L].C5-seg[R].C2:seg[R].C5;seg[c].M25=Max(Max(seg[L].M25,seg[R].M25),Max(seg[L].R25+seg[R].L5,seg[R].L25+seg[L].R2));seg[c].L25=Max(seg[L].L25,Max(seg[L].C2+seg[L].C5+seg[R].L5,seg[L].C2-seg[L].C5+seg[R].L25));seg[c].R25=Max(seg[R].R25,Max(seg[R].C2+seg[R].C5+seg[L].R2,seg[R].C5-seg[R].C2+seg[L].R25));seg[c].L5=Max(seg[L].L5,seg[L].C5-seg[L].C2+seg[R].L5);seg[c].R2=Max(seg[R].R2,seg[R].C2-seg[R].C5+seg[L].R2);
}
void build(int c,int l,int r)
{if(l==r) { seg[c].init(l); return; }int mid=l+r>>1;build(ls(c),l,mid);build(rs(c),mid+1,r);push_up(c);
}
void modify(int c,int l,int r,int x)
{if(l==r) { seg[c].init(l); return; }int mid=l+r>>1;if(x<=mid) modify(ls(c),l,mid,x);else       modify(rs(c),mid+1,r,x);push_up(c);
}
int main()
{scanf("%d",&n);top=0; tot=1; black=n;for(int i=1,x,y;i<n;i++){scanf("%d%d",&x,&y);edge(x,y);}dfs(1);build(1,1,top);scanf("%d",&m);while(m--){scanf("%s",s);if(s[0]=='G'){if(black==0) printf("-1\n");else if(black==1) printf("0\n");else printf("%d\n",seg[1].M25);}else{int x;scanf("%d",&x);black+=b[x]?1:-1;b[x]=!b[x];modify(1,1,top,pos[x]);}}return 0;
}

动态树分治代码：

#include <cstdio>
#include <algorithm>
#include <queue>
#define N 120000
using namespace std;
const int INF=0x3f3f3f3f;
class Heap{
private:priority_queue<int> R,D;int sz;
public:void push(int x) { R.push(x); sz++; }void pop(int x) { D.push(x); sz--; }int top(){while(!D.empty() && R.top()==D.top()) R.pop(),D.pop();return R.top();}int top2(){int tmp=top(),ans;pop(tmp);ans=tmp+top();push(tmp);return ans;}int size() { return sz; }
}A,B[N],C[N];
int fa[N],sz[N],zon[N],pa[N][18],dep[N];
int fir[N],nes[N<<1],v[N<<1],tot=1;
int n,m,black,root,rtf,sum;
bool mark[N],vis[N];
char opt[5];void edge(int x,int y)
{tot++;v[tot]=y;nes[tot]=fir[x];fir[x]=tot;return;
}
#define edge(x,y) edge(x,y),edge(y,x)
void dfs(int c)
{dep[c]=dep[pa[c][0]]+1;for(int i=1;i<=17;i++)pa[c][i]=pa[pa[c][i-1]][i-1];for(int t=fir[c];t;t=nes[t]){if(v[t]==pa[c][0]) continue;pa[v[t]][0]=c;dfs(v[t]);}
}
int lca(int x,int y)
{if(dep[x]<dep[y]) swap(x,y);for(int i=17;~i;i--)if(dep[pa[x][i]]>=dep[y]) x=pa[x][i];if(x==y) return x;for(int i=17;~i;i--)if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i];return pa[x][0];
}
int Distance(int x,int y)
{int LCA=lca(x,y);return dep[x]+dep[y]-(dep[LCA]<<1);
}
void find_focus(int c,int fa)
{sz[c]=1; zon[c]=0;for(int t=fir[c];t;t=nes[t]){if(vis[v[t]] || v[t]==fa) continue;find_focus(v[t],c);sz[c]+=sz[v[t]];if(sz[v[t]]>zon[c]) zon[c]=sz[v[t]];}if(sum-sz[c]>zon[c]) zon[c]=sum-sz[c];if(zon[c]<zon[root]) root=c,rtf=fa;
}
void dfs(int c,int pa)
{C[root].push(Distance(fa[root],c));for(int t=fir[c];t;t=nes[t]){if(v[t]==pa || vis[v[t]]) continue;dfs(v[t],c);}
}
void solve(int c)
{vis[c]=true;dfs(c,0);for(int t=fir[c];t;t=nes[t]){if(vis[v[t]]) continue;root=0; sum=sz[v[t]];find_focus(v[t],0);sz[rtf]=sum-sz[root];fa[root]=c;int tmp=root;solve(root);B[c].push(C[tmp].top());}B[c].push(0);if(B[c].size()>1) A.push(B[c].top2());
}
void Get_Tree()
{root=0; sum=n; zon[0]=INF;find_focus(1,0);sz[rtf]=sum-sz[root];solve(root);
}
void Reverse(int c,int x)
{if(c==x){if(B[c].size()>1) A.pop(B[c].top2());if(mark[x]) B[c].push(0);else        B[c].pop(0);if(B[c].size()>1) A.push(B[c].top2());}int tmp=fa[c];if(!tmp) return;if(B[tmp].size()>1) A.pop(B[tmp].top2());if(C[c].size()) B[tmp].pop(C[c].top());if(mark[x]) C[c].push(Distance(tmp,x));else        C[c].pop(Distance(tmp,x));if(C[c].size()) B[tmp].push(C[c].top());if(B[tmp].size()>1) A.push(B[tmp].top2());if(tmp) Reverse(tmp,x);
}
int main()
{scanf("%d",&n); black=n;for(int i=1,x,y;i<n;i++){scanf("%d%d",&x,&y);edge(x,y);}dfs(1);Get_Tree();scanf("%d",&m);while(m--){scanf("%s",opt);if(opt[0]=='C'){int x;scanf("%d",&x);Reverse(x,x);if(mark[x]) black++;else        black--;mark[x]=!mark[x];}else{if(black<=1) printf("%d\n",black-1);else printf("%d\n",A.top());}}return 0;
}

这篇关于括号序列 || 动态树分治 bzoj1095【ZJOI2007】Hide 捉迷藏的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---