问题分析

本题要求维护一棵树上的动态宠物分布状态，并快速计算最小割边数使得猫和狗不能相遇。

关键观察

问题转化：危险级别 = 最小割边数使得猫狗分离

树形结构：在树上，这等价于找到包含所有猫或所有狗的最小连通子图的边数

动态维护：需要支持单点状态修改（养猫/养狗/移除）

核心算法：动态树形DP

状态定义

对于每个节点 $u$，定义：

• $f[u][0]$：$u$ 的子树中，$u$ 所在连通块包含猫的最小割边数

• $f[u][1]$：$u$ 的子树中，$u$ 所在连通块包含狗的最小割边数

矩阵化DP转移

struct matr {
    LL mx[2][2];  // mx[i][j]: 从状态i转移到状态j的最小代价
    void set(int x = 0) {
        rep(i, 0, 1) rep(j, 0, 1) mx[i][j] = inf;
        if (x) rep(i, 0, 1) mx[i][i] = 0;  // 单位矩阵
    }
    matr operator * (matr A) const {
        matr B; B.set(0);
        rep(i,0,1) rep(j,0,1) rep(k,0,1)
            B.mx[i][j] = min(B.mx[i][j], mx[i][k] + A.mx[k][j]);
        return B;
    }
};

树链剖分优化

void dfs1(int u, int Fa) {
    siz[u] = 1;
    for(int v:e[u]) if(v!=Fa) {
        dfs1(v,u);
        siz[u] += siz[v];
        if(siz[v] >= siz[zsn[u]]) zsn[u] = v;  // 找重儿子
    }
}

平衡树维护重链

平衡树结构

struct bst {
    int c[N][2], fa[N];      // 平衡树左右儿子和父亲
    matr vw[N], ml[N];       // 节点矩阵和子树矩阵积
    int rT;                  // 根节点
    
    void pushup(int p) {
        ml[p] = ml[c[p][0]] * vw[p] * ml[c[p][1]];  // 合并矩阵
    }
};

矩阵初始化

void setw(int u) {
    vw[u].set();
    if(fo[u] != 1)  // 可以选猫
        vw[u].mx[0][0] = f[u][0], vw[u].mx[1][0] = f[u][0] + 1;
    if(fo[u] != 0)  // 可以选狗  
        vw[u].mx[1][1] = f[u][1], vw[u].mx[0][1] = f[u][1] + 1;
}

算法流程

1.初始化阶段

void initialize(int n2, vector<int> A, vector<int> B) {
    n = n2;
    // 建图
    rep(i,0,n-2) e[A[i]].push_back(B[i]), e[B[i]].push_back(A[i]);
    T.ml[0].set(1);     // 单位矩阵初始化
    dfs1(1,0);          // 树链剖分预处理
    T.init();           // 平衡树初始化
    T.rT = T.build(1);  // 构建平衡树
}

2.状态更新

void Mdf(int p, int op) {
    fo[p] = op;         // 更新节点状态
    setw(p);            // 重新计算节点矩阵
    
    for(int t=p; t; t=fa[t]) {
        if(isr(t) && fa[t]) {
            // 轻儿子更新父节点
            int fp = fa[t];
            f[fp][0] -= ml[t].gmx(0);
            f[fp][1] -= ml[t].gmx(1);
            pushup(t);
            f[fp][0] += ml[t].gmx(0);
            f[fp][1] += ml[t].gmx(1);
            setw(fp);
        } else {
            pushup(t);  // 重链内更新
        }
    }
}

3.查询操作

int cat(int u) {
    T.Mdf(u, 0);       // 设置为猫
    return T.ggmx();   // 返回全局最小值
}
int dog(int u) {
    T.Mdf(u, 1);       // 设置为狗
    return T.ggmx();
}
int neighbor(int u) {
    T.Mdf(u, 2);       // 移除宠物
    return T.ggmx();
}

复杂度分析

• 预处理：$O(n)$ 树链剖分

• 每次修改：$O(\log^2 n)$（平衡树深度 × 矩阵乘法）

• 查询：$O(1)$（根节点存储全局答案）

• 总复杂度：$O(n + q\log^2 n)$，可处理 $10^5$ 数据规模

总结

本题通过树链剖分 + 动态DP + 平衡树的复合数据结构，高效解决了树上动态最小割问题。算法的核心创新点：

• 矩阵化DP：将树形DP转化为矩阵乘法，支持快速更新

• 链式分解：利用树链剖分将问题分解到链上处理

• 平衡维护：在每条链上用平衡树维护矩阵乘积，保证复杂度

• 轻重重算：巧妙处理轻儿子对父节点的影响

AC代码

#include <bits/stdc++.h>
typedef long long LL;
#define rep(i,l,r) for(int i=l;i<=r;i++)
using namespace std;
#include "catdog.h"
const int N = 1e5 + 5, inf = 1e9;
int n;
vector<int> e[N];
LL f[N][2];
int fo[N];
struct matr {
    LL mx[2][2];
    void set(int x = 0) {
        rep(i, 0, 1) rep(j, 0, 1) mx[i][j] = inf;

        if (x)
            rep(i, 0, 1) mx[i][i] = 0;
    }
    matr operator * (matr A) const {
        matr B;
        B.set(0);
        rep(i, 0, 1) rep(j, 0, 1) rep(k, 0, 1)
        B.mx[i][j] = min(B.mx[i][j], mx[i][k] + A.mx[k][j]);
        return B;
    }
    inline LL gmx(int o) {
        return min(mx[o][0], mx[o][1]);
    }
};
int siz[N], zsn[N];
void dfs1(int u, int Fa) {
    siz[u] = 1;

    for (int v : e[u])
        if (v != Fa) {
            dfs1(v, u);
            siz[u] += siz[v];

            if (siz[v] >= siz[zsn[u]])
                zsn[u] = v;
        }
}
struct bst {
    int c[N][2], fa[N], b[N], tp, lsz[N];
    bool bv[N];
    matr vw[N], ml[N];
    int rT;
    inline void pushup(int p) {
        ml[p] = ml[c[p][0]] * vw[p] * ml[c[p][1]];
    }
    inline bool isr(const int p) {
        return c[fa[p]][1] != p && c[fa[p]][0] != p;
    }
    inline void gtw(int x, int y) {
        vw[x].mx[0][0] += ml[y].gmx(0);
        vw[x].mx[0][1] = vw[x].mx[0][0] + 1;
        vw[x].mx[1][1] += ml[y].gmx(1);
        vw[x].mx[1][0] = vw[x].mx[1][1] + 1;
        fa[y] = x;
    }
    void setw(int u) {
        vw[u].set();

        if (fo[u] != 1)
            vw[u].mx[0][0] = f[u][0], vw[u].mx[1][0] = f[u][0] + 1;

        if (fo[u] != 0)
            vw[u].mx[1][1] = f[u][1], vw[u].mx[0][1] = f[u][1] + 1;
    }
    void init() {
        for (int i = 1; i <= n; i++)
            fo[i] = 2, setw(i), ml[i] = vw[i];
    }
    int sbuild(int l, int r) {
        if (l > r)
            return 0;

        int s = 0;

        for (int i = l; i <= r; i++)
            s += lsz[b[i]];

        for (int i = l, ss = lsz[b[i]]; i <= r; i++, ss += lsz[b[i]])
            if (2 * ss >= s) {
                int lc = sbuild(l, i - 1), rc = sbuild(i + 1, r), u = b[i];
                c[u][0] = lc;
                c[u][1] = rc;
                fa[lc] = u;
                fa[rc] = u;
                pushup(u);
                return u;
            }

        return 0;
    }
    int build(int p) {
        for (int i = p; i; i = zsn[i])
            bv[i] = 1;

        for (int i = p; i; i = zsn[i])
            for (int j : e[i])
                if (!bv[j])
                    gtw(i, build(j));

        tp = 0;

        for (int i = p; i; i = zsn[i])
            b[++tp] = i, lsz[i] = siz[i] - siz[zsn[i]];

        return sbuild(1, tp);
    }
    inline void Mdf(int p, int op) {
        fo[p] = op;
        setw(p);

        for (int t = p; t; t = fa[t]) {
            if (isr(t) && fa[t]) {
                int fp = fa[t];
                f[fp][0] -= ml[t].gmx(0);
                f[fp][1] -= ml[t].gmx(1);
                pushup(t);
                f[fp][0] += ml[t].gmx(0);
                f[fp][1] += ml[t].gmx(1);
                setw(fp);
            } else
                pushup(t);
        }
    }
    inline LL ggmx() {
        return min(ml[rT].gmx(0), ml[rT].gmx(1));
    }
} T;
void initialize(int n2, std::vector<int> A, std::vector<int> B) {
    n = n2;
    rep(i, 0, n - 2)
    e[A[i]].push_back(B[i]), e[B[i]].push_back(A[i]);
    T.ml[0].set(1);
    dfs1(1, 0);
    T.init();
    T.rT = T.build(1);
}
int cat(int u) {
    T.Mdf(u, 0);
    return T.ggmx();
}
int dog(int u) {
    T.Mdf(u, 1);
    return T.ggmx();
}
int neighbor(int u) {
    T.Mdf(u, 2);
    return T.ggmx();
}