C138 线段树分治+LCA P2056 [ZJOI2007] 捉迷藏

// 线段树分治 O(nlognlogn)
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <bitset>
using namespace std;

#define ls (i<<1)
#define rs (i<<1|1)
#define mid ((l+r)>>1)
const int N=500005;
int n,q;
int head[N],ne[N<<1],to[N<<1],idx;
void add(int u,int v){
  to[++idx]=v;ne[idx]=head[u];
  head[u]=idx;
}
int fa[N],son[N],dep[N],siz[N],top[N];

void dfs1(int u,int f){ //搞fa,son,dep
  fa[u]=f;siz[u]=1;dep[u]=dep[f]+1;
  for(int i=head[u];i;i=ne[i]){
    int v=to[i];
    if(v==f) continue;
    dfs1(v,u);
    siz[u]+=siz[v];
    if(siz[son[u]]<siz[v])son[u]=v;
  }
}
void dfs2(int u,int t){ //搞top
  top[u]=t;  //记录链头
  if(son[u])dfs2(son[u],t);//搜重儿子
  for(int i=head[u];i;i=ne[i]){
    int v=to[i];
    if(v==fa[u]||v==son[u])continue;
    dfs2(v,v); //搜轻儿子
  }
}
int lca(int u,int v){
  while(top[u]!=top[v]){
    if(dep[top[u]]<dep[top[v]])swap(u,v);
    u=fa[top[u]];
  }
  return dep[u]<dep[v]?u:v;
}

int lst[N];    //上次出现的时刻
bitset<N> col; //黑色=0
bitset<N> qb;  //查询=1
vector<int> tr[N<<2];   //节点
stack<pair<int,int>>st; //栈
int u,v,ans[N];

void insert(int i,int l,int r,int L,int R,int x){
  if(L>r||R<l) return;
  if(L<=l&&r<=R) return tr[i].push_back(x);
  insert(ls,l,mid,L,R,x);
  insert(rs,mid+1,r,L,R,x);
}
int dis(int x,int y){ //两点距离
  return dep[x]+dep[y]-2*dep[lca(x,y)];
}
void solve(int i,int l,int r){
  auto now=st.size();
  for(int x:tr[i]){
    st.push({u,v}); //旧直径入栈
    if(!u&&!v) u=x,v=x;
    else{
      int d0=dis(u,v),d1=dis(u,x),d2=dis(v,x);
      int d=max(d0,max(d1,d2));
      if(d1==d) v=x;
      else if(d2==d) u=x; //更新直径端点
    }
  }
  
  if(l==r) ans[l]=(!u||!v)?-1:dis(u,v);
  else solve(ls,l,mid),solve(rs,mid+1,r);
  
  while(st.size()!=now){ //撤销
    auto t=st.top();
    u=t.first,v=t.second;
    st.pop();
  }
}
int main(){
  ios::sync_with_stdio(false);
  cin>>n;
  for(int i=1,u,v;i<n;i++){
    cin>>u>>v; add(u,v);add(v,u);
  }
  dfs1(1,0);dfs2(1,0); //树链剖分
  
  for(int i=1;i<=n;i++) lst[i]=1;
  cin>>q;
  for(int i=1,x;i<=q;i++){ //操作为时间轴
    char c; cin>>c;
    if(c=='C'){
      cin>>x;
      if(!col[x]){ //黑色=0
        col[x]=1;
        insert(1,1,q,lst[x],i,x); //插入x的出现时间
      }
      else col[x]=0,lst[x]=i; //记录x再次出现时刻
    }
    else qb[i]=1; //i时刻是查询
  }
  for(int i=1;i<=n;i++) //插入i的出现时间
    if(!col[i]) insert(1,1,q,lst[i],q,i);
  solve(1,1,q);
  for(int i=1;i<=q;i++)
    if(qb[i])printf("%d\n",ans[i]);
}

P2056 [ZJOI2007] 捉迷藏

题目描述

给定一棵n个节点的树，每个节点有一个初始颜色（0或1），支持两种操作：1. 改变一个节点的颜色；2. 查询当前树中所有颜色为1的节点之间的最大距离（即直径）。

解题思路

• 线段树分治处理动态颜色变化与查询
• LCA预处理计算节点距离
• 维护颜色为1的节点集合的直径端点

算法步骤

1. 预处理LCA（倍增法），计算节点深度与距离
2. 构建操作序列的线段树分治结构
3. 分治节点中维护颜色为1的节点集合，计算直径
4. 回溯撤销操作，合并子区间结果

代码实现

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

const int MAXN = 100010;
const int LOG = 20;

vector<int> adj[MAXN];
int depth[MAXN], up[LOG][MAXN];
int n, m;
int color[MAXN];
int ans;

// LCA预处理
void dfs(int u, int parent) {
    up[0][u] = parent;
    depth[u] = depth[parent] + 1;
    for (int i = 1; i < LOG; ++i)
        up[i][u] = up[i-1][up[i-1][u]];
    for (int v : adj[u]) {
        if (v != parent)
            dfs(v, u);
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];
    for (int i = 0; i < LOG; ++i)
        if (diff & (1 << i))
            u = up[i][u];
    if (u == v) return u;
    for (int i = LOG-1; i >= 0; --i)
        if (up[i][u] != up[i][v])
            u = up[i][u], v = up[i][v];
    return up[0][u];
}

int distance(int u, int v) {
    int ancestor = lca(u, v);
    return depth[u] + depth[v] - 2 * depth[ancestor];
}

// 线段树分治节点
struct Node {
    int l, r;
    vector<int> nodes; // 颜色为1的节点
    Node *left, *right;
    Node(int l, int r) : l(l), r(r), left(nullptr), right(nullptr) {}
};

// 构建线段树分治
Node* build(int l, int r, vector<pair<int, int>>& ops) {
    Node* node = new Node(l, r);
    if (l == r) return node;
    int mid = (l + r) / 2;
    node->left = build(l, mid, ops);
    node->right = build(mid+1, r, ops);
    return node;
}

// 处理分治节点
void process(Node* node, vector<pair<int, int>>& ops, vector<int>& res) {
    // 应用该区间内的所有颜色变化操作
    for (int i = node->l; i <= node->r; ++i) {
        if (ops[i].first == 1) { // 颜色变化操作
            int u = ops[i].second;
            if (color[u] == 1) {
                node->nodes.erase(find(node->nodes.begin(), node->nodes.end(), u));
            } else {
                node->nodes.push_back(u);
            }
            color[u] ^= 1;
        }
    }

    // 计算当前颜色为1的节点的直径
    if (node->nodes.size() < 2) {
        res.push_back(0);
    } else {
        // 找最远点u
        int u = node->nodes[0];
        for (int v : node->nodes)
            if (distance(u, v) > distance(u, node->nodes[0]))
                u = v;
        // 找最远点v
        int v = node->nodes[0];
        for (int w : node->nodes)
            if (distance(w, u) > distance(v, u))
                v = w;
        res.push_back(distance(u, v));
    }

    // 递归处理子节点
    if (node->left) {
        process(node->left, ops, res);
        process(node->right, ops, res);
    }

    // 撤销颜色变化操作（回溯）
    for (int i = node->l; i <= node->r; ++i) {
        if (ops[i].first == 1) {
            int u = ops[i].second;
            color[u] ^= 1;
        }
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n-1; ++i) {
        int u, v;
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0); // 根节点为1，父节点为0

    scanf("%d", &m);
    vector<pair<int, int>> ops(m+1); // 1-based
    for (int i = 1; i <= m; ++i) {
        scanf("%d %d", &ops[i].first, &ops[i].second);
    }

    Node* root = build(1, m, ops);
    vector<int> res;
    process(root, ops, res);

    // 输出结果（实际需根据分治逻辑合并结果）
    // ...

    return 0;
}

（注：实际代码需根据具体视频讲解调整，此处为核心逻辑框架，可能需补充分治结果合并、初始颜色设置等细节）