BZOJ1095 [ZJOI2007]Hide 捉迷藏【动态点分治 + 堆】-白红宇

BZOJ1095 [ZJOI2007]Hide 捉迷藏【动态点分治 + 堆】

阅读量：5037 次

发布时间：2019-06-12

本文共 4268 字，大约阅读时间需要 14 分钟。

题目链接

题解

传说中的动态点分治，一直不敢碰

今日一会，感觉其实并不艰涩难懂

考虑没有修改，如果不用树形dp的话，就得点分治

对于每个重心，我们会考虑其分治的子树内所有点到它的距离，然后取所有不同子树中最大的两个相加来更新答案

如果带修改怎么办呢？

考虑一个点\(u\)被修改了，会对哪些点产生影响。显然是包含它的分治子树之中

点分树

我们在点分治过程中，将每个重心与上一层分治重心相连，形成一棵树结构，叫做点分树

一个点被修改，仅影响其在点分树中所有祖先的答案

那么这样我们就可以维护了

对于每个点\(u\)，我们开两个堆分别储存一下信息：

堆\(C\)：以\(C\)为根的分治子树中所有点到点分树中\(u\)的父亲的距离

堆\(B\)：\(u\)在点分树中所有儿子\(C\)堆堆顶

对于全局开一个堆\(A\)，储存所有堆\(B\)的最大值和次大值之和

那么堆\(A\)堆顶就是当前的答案

对于堆来说，插入是很方便的，但是删除就没那么简单，我们可以对每个堆再开一个堆，储存所有被删除的值，每次访问堆顶时，如果删除堆堆顶与当前堆顶相同，那么都\(pop\)掉，直到不相同位置

还要注意的就是堆间操作的顺序

我们要操作\(C\)，就得先将父亲\(B\)堆中该\(C\)堆堆顶\(pop\)掉，操作完再加回去

同样，我们要操作\(B\)，也得先从\(A\)中将对应贡献删除

感觉这题难点并不在动态点分治。。。而是在堆的维护吧。。。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)#define REP(i,n) for (int i = 1; i <= (n); i++)#define mp(a,b) make_pair
           
            (a,b)#define cls(s) memset(s,0,sizeof(s))#define cp pair
            
             #define LL long long intusing namespace std;const int maxn = 100005,maxm = 200005,INF = 1000000000;inline int read(){ int out = 0,flag = 1; char c = getchar(); while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();} while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();} return out * flag;}struct heap{ priority_queue
             
               a,b; void ins(int x){if (x >= 0) a.push(x);} void del(int x){if (x >= 0) b.push(x);} int size(){return a.size() - b.size();} int top(){ if (!size()) return -1; while (!b.empty() && a.top() == b.top()) a.pop(),b.pop(); return a.top(); } int sum(){ if (size() < 2) return -1; int x = top(); a.pop(); int y = top(); ins(x); return x + y; }}C[maxn],B[maxn],A;int bin[50],Log[maxm],mn[maxm][19];int n,fa[maxn],dep[maxn],dfn[maxn],cnt;int h[maxn],ne = 1;struct EDGE{int to,nxt;}ed[maxn << 1];void build(int u,int v){ ed[++ne] = (EDGE){v,h[u]}; h[u] = ne; ed[++ne] = (EDGE){u,h[v]}; h[v] = ne;}void dfs(int u){ mn[++cnt][0] = dep[u]; dfn[u] = cnt; Redge(u) if ((to = ed[k].to) != fa[u]){ fa[to] = u; dep[to] = dep[u] + 1; dfs(to); mn[++cnt][0] = dep[u]; }}int dis(int u,int v){ int l = dfn[u],r = dfn[v]; if (l > r) swap(l,r); int t = Log[r - l + 1]; int d = min(mn[l][t],mn[r - bin[t] + 1][t]); return dep[u] + dep[v] - (d << 1);}int F[maxn],Siz[maxn],vis[maxn],Fa[maxn],sum,rt;int pre[maxn];void getrt(int u){ F[u] = 0; Siz[u] = 1; Redge(u) if (!vis[to = ed[k].to] && to != Fa[u]){ Fa[to] = u; getrt(to); Siz[u] += Siz[to]; F[u] = max(F[u],Siz[to]); } F[u] = max(F[u],sum - Siz[u]); if (F[u] < F[rt]) rt = u;}int c[maxn],ci;void dfs1(int u){ Siz[u] = 1; c[++ci] = u; Redge(u) if (!vis[to = ed[k].to] && to != Fa[u]){ Fa[to] = u; dfs1(to); Siz[u] += Siz[to]; }}void solve(int u){ vis[u] = true; Siz[u] = 1; ci = 0; Redge(u) if (!vis[to = ed[k].to]){ Fa[to] = u; dfs1(to); Siz[u] += Siz[to]; } if (pre[u]){ C[u].ins(dis(u,pre[u])); REP(i,ci) C[u].ins(dis(c[i],pre[u])); } Redge(u) if (!vis[to = ed[k].to]){ F[rt = 0] = INF; sum = Siz[to]; getrt(to); pre[rt] = u; to = rt; solve(rt); B[u].ins(C[to].top()); } B[u].ins(0); A.ins(B[u].sum());}int light[maxn];void Insert(int x){ int v; A.del(B[x].sum()); B[x].ins(0); A.ins(B[x].sum()); for (int u = x; pre[u]; u = pre[u]){ v = pre[u]; A.del(B[v].sum()); B[v].del(C[u].top()); C[u].ins(dis(x,v)); B[v].ins(C[u].top()); A.ins(B[v].sum()); }}void Delete(int x){ int v; A.del(B[x].sum()); B[x].del(0); A.ins(B[x].sum()); for (int u = x; pre[u]; u = pre[u]){ v = pre[u]; A.del(B[v].sum()); B[v].del(C[u].top()); C[u].del(dis(x,v)); B[v].ins(C[u].top()); A.ins(B[v].sum()); }}int main(){ bin[0] = 1; for (int i = 1; i <= 25; i++) bin[i] = bin[i - 1] << 1; Log[0] = -1; for (int i = 1; i < maxm; i++) Log[i] = Log[i >> 1] + 1; n = read(); for (int i = 1; i < n; i++) build(read(),read()); dfs(1); for (int j = 1; j <= 18; j++) for (int i = 1; i <= cnt; i++){ if (i + bin[j] - 1 > cnt) break; mn[i][j] = min(mn[i][j - 1],mn[i + bin[j - 1]][j - 1]); } F[rt = 0] = INF; sum = n; getrt(1); solve(rt); int m = read(),v; char opt; while (m--){ opt = getchar(); while (opt != 'G' && opt != 'C') opt = getchar(); if (opt == 'G'){ v = A.top(); printf("%d\n",v >= 0 ? v : -1); } else { v = read(); light[v] ^= 1; if (!light[v]) Insert(v); else Delete(v); } } return 0;}

转载于:https://www.cnblogs.com/Mychael/p/9056715.html

你可能感兴趣的文章