线段树

已知一个数列，你需要进行下面两种操作：
将某区间每一个数加上 𝑘
k。
求出某区间每一个数的和。
#include <iostream>
#include <bits/stdc++.h>
using LL = long long;
LL n, a[100005], d[270000], b[270000];

void build(LL l, LL r, LL p) {  // l:区间左端点 r:区间右端点 p:节点标号
  if (l == r) {
    d[p] = a[l];  // 将节点赋值
    return;
  }
  LL m = l + ((r - l) >> 1);
  build(l, m, p << 1), build(m + 1, r, (p << 1) | 1);  // 分别建立子树
  d[p] = d[p << 1] + d[(p << 1) | 1];
}

void update(LL l, LL r, LL c, LL s, LL t, LL p) {
  if (l <= s && t <= r) {
    d[p] += (t - s + 1) * c, b[p] += c;  // 如果区间被包含了，直接得出答案
    return;
  }
  LL m = s + ((t - s) >> 1);
  if (b[p])
    d[p << 1] += b[p] * (m - s + 1), d[(p << 1) | 1] += b[p] * (t - m),
        b[p << 1] += b[p], b[(p << 1) | 1] += b[p];
  b[p] = 0;
  if (l <= m)
    update(l, r, c, s, m, p << 1);  // 本行和下面的一行用来更新p*2和p*2+1的节点
  if (r > m) update(l, r, c, m + 1, t, (p << 1) | 1);
  d[p] = d[p << 1] + d[(p << 1) | 1];  // 计算该节点区间和
}

LL getsum(LL l, LL r, LL s, LL t, LL p) {
  if (l <= s && t <= r) return d[p];
  LL m = s + ((t - s) >> 1);
  if (b[p])
    d[p << 1] += b[p] * (m - s + 1), d[(p << 1) | 1] += b[p] * (t - m),
        b[p << 1] += b[p], b[(p << 1) | 1] += b[p];
  b[p] = 0;
  LL sum = 0;
  if (l <= m)
    sum =
        getsum(l, r, s, m, p << 1);  // 本行和下面的一行用来更新p*2和p*2+1的答案
  if (r > m) sum += getsum(l, r, m + 1, t, (p << 1) | 1);
  return sum;
}

int main() {
  std::ios::sync_with_stdio(false);
  LL q, i1, i2, i3, i4;
  std::cin >> n >> q;
  for (LL i = 1; i <= n; i++) std::cin >> a[i];
  build(1, n, 1);
  while (q--) {
    std::cin >> i1 >> i2 >> i3;
    if (i1 == 2)
      std::cout << getsum(i2, i3, 1, n, 1) << std::endl;  // 直接调用操作函数
    else
      std::cin >> i4, update(i2, i3, i4, 1, n, 1);
  }
  return 0;
}

已知一个数列，你需要进行下面三种操作：
将某区间每一个数乘上 x
将某区间每一个数加上 𝑥
求出某区间每一个数的和。
#include <iostream>
using ll = long long;

int n, m;
ll mod;
ll a[100005], sum[400005], mul[400005], laz[400005];

void up(int i) { sum[i] = (sum[(i << 1)] + sum[(i << 1) | 1]) % mod; }

void pd(int i, int s, int t) {
  int l = (i << 1), r = (i << 1) | 1, mid = (s + t) >> 1;
  if (mul[i] != 1) {  // 懒标记传递，两个懒标记
    mul[l] *= mul[i];
    mul[l] %= mod;
    mul[r] *= mul[i];
    mul[r] %= mod;
    laz[l] *= mul[i];
    laz[l] %= mod;
    laz[r] *= mul[i];
    laz[r] %= mod;
    sum[l] *= mul[i];
    sum[l] %= mod;
    sum[r] *= mul[i];
    sum[r] %= mod;
    mul[i] = 1;
  }
  if (laz[i]) {  // 懒标记传递
    sum[l] += laz[i] * (mid - s + 1);
    sum[l] %= mod;
    sum[r] += laz[i] * (t - mid);
    sum[r] %= mod;
    laz[l] += laz[i];
    laz[l] %= mod;
    laz[r] += laz[i];
    laz[r] %= mod;
    laz[i] = 0;
  }
  return;
}

void build(int s, int t, int i) {
  mul[i] = 1;
  if (s == t) {
    sum[i] = a[s];
    return;
  }
  int mid = s + ((t - s) >> 1);
  build(s, mid, i << 1);  // 建树
  build(mid + 1, t, (i << 1) | 1);
  up(i);
}

void chen(int l, int r, int s, int t, int i, ll z) {
  int mid = s + ((t - s) >> 1);
  if (l <= s && t <= r) {
    mul[i] *= z;
    mul[i] %= mod;  // 这是取模的
    laz[i] *= z;
    laz[i] %= mod;  // 这是取模的
    sum[i] *= z;
    sum[i] %= mod;  // 这是取模的
    return;
  }
  pd(i, s, t);
  if (mid >= l) chen(l, r, s, mid, (i << 1), z);
  if (mid + 1 <= r) chen(l, r, mid + 1, t, (i << 1) | 1, z);
  up(i);
}

void add(int l, int r, int s, int t, int i, ll z) {
  int mid = s + ((t - s) >> 1);
  if (l <= s && t <= r) {
    sum[i] += z * (t - s + 1);
    sum[i] %= mod;  // 这是取模的
    laz[i] += z;
    laz[i] %= mod;  // 这是取模的
    return;
  }
  pd(i, s, t);
  if (mid >= l) add(l, r, s, mid, (i << 1), z);
  if (mid + 1 <= r) add(l, r, mid + 1, t, (i << 1) | 1, z);
  up(i);
}

ll getans(int l, int r, int s, int t,
          int i) {  // 得到答案，可以看下上面懒标记助于理解
  int mid = s + ((t - s) >> 1);
  ll tot = 0;
  if (l <= s && t <= r) return sum[i];
  pd(i, s, t);
  if (mid >= l) tot += getans(l, r, s, mid, (i << 1));
  tot %= mod;
  if (mid + 1 <= r) tot += getans(l, r, mid + 1, t, (i << 1) | 1);
  return tot % mod;
}

using std::cin;
using std::cout;

int main() {  // 读入
  cin.tie(nullptr)->sync_with_stdio(false);
  int i, j, x, y, bh;
  ll z;
  cin >> n >> m >> mod;
  for (i = 1; i <= n; i++) cin >> a[i];
  build(1, n, 1);  // 建树
  for (i = 1; i <= m; i++) {
    cin >> bh;
    if (bh == 1) {
      cin >> x >> y >> z;
      chen(x, y, 1, n, 1, z);
    } else if (bh == 2) {
      cin >> x >> y >> z;
      add(x, y, 1, n, 1, z);
    } else if (bh == 3) {
      cin >> x >> y;
      cout << getans(x, y, 1, n, 1) << '\n';
    }
  }
  return 0;
}

树状数组的区间加区间和模板
int t1[MAXN], t2[MAXN], n;

int lowbit(int x) { return x & (-x); }

void add(int k, int v) {
  int v1 = k * v;
  while (k <= n) {
    t1[k] += v, t2[k] += v1;
    // 注意不能写成 t2[k] += k * v，因为 k 的值已经不是原数组的下标了
    k += lowbit(k);
  }
}

int getsum(int *t, int k) {
  int ret = 0;
  while (k) {
    ret += t[k];
    k -= lowbit(k);
  }
  return ret;
}

void add1(int l, int r, int v) {
  add(l, v), add(r + 1, -v);  // 将区间加差分为两个前缀加
}

long long getsum1(int l, int r) {
  return (r + 1ll) * getsum(t1, r) - 1ll * l * getsum(t1, l - 1) -
         (getsum(t2, r) - getsum(t2, l - 1));
}


建树
// Θ(n) 建树
void init() {
  for (int i = 1; i <= n; ++i) {
    t[i] = sum[i] - sum[i - lowbit(i)];
  }
}

最小回文分割
int f(string s){
    vector<vector<int>> pre;
    int n = s.size();
    pre.assign(n, vector<int>(n, true));
    for(int i=n-1;i>=0;--i){
        for (int j =i+1;j<n;++j){
             pre[i][j]=(s[i]==s[j])&&pre[i+1][j-1];
        }
    }
    int ans=0;
    for(int i =0;i<n;++i){
        int j;
        for(j=n-1;j>=i;--j){
            if(pre[i][j]==1) {
                ans++;
                break;
            }
        }
        i=j;
    }
    return ans-1;
}

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <climits>
using namespace std;

struct BigInt {
    vector<int> d; 

    BigInt() {}
    BigInt(string s) {
        for (int i = s.size() - 1; i >= 0; --i)
            d.push_back(s[i] - '0');
        trim();
    }
    void trim() {
        while (d.size() > 1 && d.back() == 0) d.pop_back();
    }
    string toString() const {
        string s;
        for (int i = d.size() - 1; i >= 0; --i) s.push_back(d[i] + '0');
        return s;
    }
};

BigInt add(const BigInt &a, const BigInt &b) {
    BigInt c;
    int carry = 0;
    for (int i = 0; i < (int)max(a.d.size(), b.d.size()) || carry; ++i) {
        int x = carry;
        if (i < a.d.size()) x += a.d[i];
        if (i < b.d.size()) x += b.d[i];
        c.d.push_back(x % 10);
        carry = x / 10;
    }
    c.trim();
    return c;
}

bool lessThan(const BigInt &a, const BigInt &b) {
    if (a.d.size() != b.d.size()) return a.d.size() < b.d.size();
    for (int i = a.d.size() - 1; i >= 0; --i)
        if (a.d[i] != b.d[i])
            return a.d[i] < b.d[i];
    return false;
}

BigInt f(int n, const string &s) {
    int l = s.size();
    vector<vector<BigInt>> dp(l, vector<BigInt>(n));
    vector<vector<bool>> ok(l, vector<bool>(n, false)); 

    for (int i = 0; i < l; ++i) {
        dp[i][0] = BigInt(s.substr(0, i + 1));
        ok[i][0] = true;
    }

    for (int i = 0; i < l; ++i) {
        for (int j = 1; j < n; ++j) {
            if (j > i) continue;
            BigInt best; bool first = true;
            for (int k = j - 1; k < i; ++k) {
                if (!ok[k][j - 1]) continue;
                BigInt right(s.substr(k + 1, i - k));
                BigInt val = add(dp[k][j - 1], right);
                if (first || lessThan(val, best)) {
                    best = val;
                    first = false;
                }
            }
            if (!first) {
                dp[i][j] = best;
                ok[i][j] = true;
            }
        }
    }

    return dp[l - 1][n - 1];
}

int main() {
    int n;
    string s;
    while (cin >> n >> s) {
        cout << f(n+1, s).toString() << endl;
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

struct Node {
    int x, y, mask, dist;
};

int R, C, K;
char mp[205][205];
bool vis[205][205][1 << 5];
vector<pair<int,int>> portals;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int bitcount(int x) {
    int cnt = 0;
    while (x) {
        cnt += (x & 1);
        x >>= 1;
    }
    return cnt;
}
int bfs(int sx, int sy, int ex, int ey) {
    memset(vis, 0, sizeof(vis));
    deque<Node> q;
    q.push_back({sx, sy, 0, 0});
    vis[sx][sy][0] = true;

    while(!q.empty()) {
        Node cur = q.front(); q.pop_front();

        if (cur.x == ex && cur.y == ey) {
            if (bitcount(cur.mask) >= K)
                return cur.dist;
        }
        for (int i = 0; i < 4; ++i) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            if (nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
            char c = mp[nx][ny];
            if (c == '#') continue;

            int new_mask = cur.mask;
            if (c >= '0' && c <= '4')
                new_mask |= (1 << (c - '0'));

            if (!vis[nx][ny][new_mask]) {
                vis[nx][ny][new_mask] = true;
                q.push_back({nx, ny, new_mask, cur.dist + 1});
            }
        }
        if (mp[cur.x][cur.y] == '$') {
            for (auto [px, py] : portals) {
                if (px == cur.x && py == cur.y) continue;
                if (!vis[px][py][cur.mask]) {
                    vis[px][py][cur.mask] = true;
                    q.push_front({px, py, cur.mask, cur.dist}); 
                }
            }
        }
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T; cin >> T;
    while (T--) {
        cin >> R >> C >> K;
        portals.clear();
        int sx, sy, ex, ey;

        for (int i = 0; i < R; ++i) {
            cin >> mp[i];
            for (int j = 0; j < C; ++j) {
                if (mp[i][j] == 'S') sx = i, sy = j;
                else if (mp[i][j] == 'E') ex = i, ey = j;
                else if (mp[i][j] == '$') portals.push_back({i,j});
            }
        }

        int res = bfs(sx, sy, ex, ey);
        if (res == -1) cout << "oop!\n";
        else cout << res << "\n";
    }
    return 0;
}

树形dp
#include<iostream>
#include <vector>
#include<array>
#include <algorithm>
using namespace std;
using ll = long long;

int N; 
vector<vector<int>> adj; 
vector<array<ll,3>> dp;  
void dfs(int u, int parent){
    bool isLeaf = true;
    ll sum_min012 = 0; 
    ll sum_dp1 = 0;    
    ll sum_min12 = 0;  
    vector<int> children;
    for(int v: adj[u]){
        if(v == parent) continue;
        isLeaf = false;
        dfs(v, u);
        children.push_back(v);
        sum_min012 += min({dp[v][0], dp[v][1], dp[v][2]});
        sum_dp1 += dp[v][1];
        sum_min12 += min(dp[v][1], dp[v][2]);
    }
    if(isLeaf){
        dp[u][0] = 0;    
        dp[u][1] = 1e9;  
        dp[u][2] = 1;    
        return;
    }
    dp[u][2] = 1 + sum_min012;
    dp[u][0] = sum_dp1;
    ll best = 1e9;
    for(int v: children){
        ll cand = sum_min12 - min(dp[v][1], dp[v][2]) + dp[v][2];
        best = min(best, cand);
    }
    dp[u][1] = best;
}

int main(){
    cin >> N;
    adj.assign(N+1, vector<int>());
    dp.assign(N+1, {0,0,0});
    for(int i=0;i<N-1;++i){
        int u,v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1, 0); 
    cout << min(dp[1][1], dp[1][2]) << "\n"; 
    return 0;
}

#include <iostream>
#include <numeric>
#include <vector>
#include <unordered_map>
using ll = long long;
using namespace std;

struct  Edge
{
    int u,v;//  u->v
    ll w;
};

ll minArborescenceSubset(const vector<int>& nodes, int root, const vector<Edge>& edges){
    int n = nodes.size();
    unordered_map<int,int> idx;//将node映射成int型数字
    for(int i=0;i<n;++i) idx[nodes[i]]=i;

    vector<Edge> es;//记录全部的合法边，及边的两端的节点都可从root到达
    for(auto &e:edges){
        if(idx.count(e.u)&&idx.count(e.v)){
            es.push_back({idx[e.u],idx[e.v],e.w});
        }
    }
    const ll INF = 1e18;
    ll res = 0;//return
    int r = idx[root];

    vector<int> nodeIds(n);
    iota(nodeIds.begin(),nodeIds.end(),0);//给nodeIds的元素依次赋值0，1，2，3···
    //这里似乎没用到 ⬆️
    while(true){
        vector<ll> in(n,INF);//记录每个点的最小入边的权重
        vector<int> from(n,-1);//记录每个点的最小入边的出发点

        for(auto &e:es){
            if(e.u!=e.v&&e.w<in[e.v]){
                in[e.v]=e.w;
                from[e.v] = e.u;
            }
        }

        in[r]=0;//root的in设为0

        int cntnode = 0;//如果存在环，cntnode将变为压缩环后的总节点数量
        vector<int> visited(n,-1),id(n,-1);
        for(int i=0;i<n;++i){
            res += in[i];
            int v = i;//从idx为i的节点一直向前搜索，判断是否成环
            while(visited[v]!=i&&id[v]==-1&&v!=r){
                visited[v] = i;//记录一下当前的节点是从哪个节点搜索出来的
                v= from[v];//向前搜索
            }
            //通过id可以判断当前节点是否已经成为某个环的一部分
            if(id[v]==-1&&v!=r){
               //确保是因为成环才导致上面的循环结束的
               for(int u = from[v];u!=v;u = from[u]) id[u]=cntnode;
               id[v]=cntnode++; 
            }

        }
        if(cntnode==0) break;//如果没环产生，则当前即位最小树型图
        //给未成环剩余的节点从新附上id
        for(int i=0;i<n;++i){
            if(id[i]==-1) id[i]=cntnode++;
        }

        for(auto &e:es){
            e.w -= in[e.v];//这里是关键，在将环压缩成一个节点时如果存在环外的节点指向环内的节点，要将这个路径的权重减去被指向节点的最小入边的权重
            e.u = id[e.u];//因为之前在计算res时已经将被指向节点的in值记录，如果之后为了全局的最优而选择在被指向节点处断开环就得在res中减去对应的in值，
            e.v = id[e.v]; //因此直接将未来某个要减去的值提前在别的可能选中的边上减去
            }
        n =cntnode;
        r = id[r];
    }
    return res;
}

int main(){
    vector<int> nodes={1,2,3,4};
    vector<Edge> e={{1,2,3},{1,3,2},{2,3,4},{1,4,1},{4,1,2},{2,3,1}};
    int root = 1;
    cout<<minArborescenceSubset(nodes,root,e);
    return 0;

}
```cpp
/* AVL 树节点类 */
struct TreeNode {
    int val{};          // 节点值
    int height = 0;     // 节点高度
    TreeNode *left{};   // 左子节点
    TreeNode *right{};  // 右子节点
    TreeNode() = default;
    explicit TreeNode(int x) : val(x){}
};
/* 获取节点高度 */
int height(TreeNode *node) {
    // 空节点高度为 -1 ，叶节点高度为 0
    return node == nullptr ? -1 : node->height;
}

/* 更新节点高度 */
void updateHeight(TreeNode *node) {
    // 节点高度等于最高子树高度 + 1
    node->height = max(height(node->left), height(node->right)) + 1;
}
/* 获取平衡因子 */
int balanceFactor(TreeNode *node) {
    // 空节点平衡因子为 0
    if (node == nullptr)
        return 0;
    // 节点平衡因子 = 左子树高度 - 右子树高度
    return height(node->left) - height(node->right);
}
/* 右旋操作 */
TreeNode *rightRotate(TreeNode *node) {
    TreeNode *child = node->left;
    TreeNode *grandChild = child->right;
    // 以 child 为原点，将 node 向右旋转
    child->right = node;
    node->left = grandChild;
    // 更新节点高度
    updateHeight(node);
    updateHeight(child);
    // 返回旋转后子树的根节点
    return child;
}
/* 左旋操作 */
TreeNode *leftRotate(TreeNode *node) {
    TreeNode *child = node->right;
    TreeNode *grandChild = child->left;
    // 以 child 为原点，将 node 向左旋转
    child->left = node;
    node->right = grandChild;
    // 更新节点高度
    updateHeight(node);
    updateHeight(child);
    // 返回旋转后子树的根节点
    return child;
}
/* 执行旋转操作，使该子树重新恢复平衡 */
TreeNode *rotate(TreeNode *node) {
    // 获取节点 node 的平衡因子
    int _balanceFactor = balanceFactor(node);
    // 左偏树
    if (_balanceFactor > 1) {
        if (balanceFactor(node->left) >= 0) {
            // 右旋
            return rightRotate(node);
        } else {
            // 先左旋后右旋
            node->left = leftRotate(node->left);
            return rightRotate(node);
        }
    }
    // 右偏树
    if (_balanceFactor < -1) {
        if (balanceFactor(node->right) <= 0) {
            // 左旋
            return leftRotate(node);
        } else {
            // 先右旋后左旋
            node->right = rightRotate(node->right);
            return leftRotate(node);
        }
    }
    // 平衡树，无须旋转，直接返回
    return node;
}
/* 插入节点 */
void insert(int val) {
    root = insertHelper(root, val);
}

/* 递归插入节点（辅助方法） */
TreeNode *insertHelper(TreeNode *node, int val) {
    if (node == nullptr)
        return new TreeNode(val);
    /* 1. 查找插入位置并插入节点 */
    if (val < node->val)
        node->left = insertHelper(node->left, val);
    else if (val > node->val)
        node->right = insertHelper(node->right, val);
    else
        return node;    // 重复节点不插入，直接返回
    updateHeight(node); // 更新节点高度
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 返回子树的根节点
    return node;
}
/* 删除节点 */
void remove(int val) {
    root = removeHelper(root, val);
}

/* 递归删除节点（辅助方法） */
TreeNode *removeHelper(TreeNode *node, int val) {
    if (node == nullptr)
        return nullptr;
    /* 1. 查找节点并删除 */
    if (val < node->val)
        node->left = removeHelper(node->left, val);
    else if (val > node->val)
        node->right = removeHelper(node->right, val);
    else {
        if (node->left == nullptr || node->right == nullptr) {
            TreeNode *child = node->left != nullptr ? node->left : node->right;
            // 子节点数量 = 0 ，直接删除 node 并返回
            if (child == nullptr) {
                delete node;
                return nullptr;
            }
            // 子节点数量 = 1 ，直接删除 node
            else {
                delete node;
                node = child;
            }
        } else {
            // 子节点数量 = 2 ，则将中序遍历的下个节点删除，并用该节点替换当前节点
            TreeNode *temp = node->right;
            while (temp->left != nullptr) {
                temp = temp->left;
            }
            int tempVal = temp->val;
            node->right = removeHelper(node->right, temp->val);
            node->val = tempVal;
        }
    }
    updateHeight(node); // 更新节点高度
    /* 2. 执行旋转操作，使该子树重新恢复平衡 */
    node = rotate(node);
    // 返回子树的根节点
    return node;
}
```cpp
/* 加法哈希 */
int addHash(string key) {
    long long hash = 0;
    const int MODULUS = 1000000007;
    for (unsigned char c : key) {
        hash = (hash + (int)c) % MODULUS;
    }
    return (int)hash;
}

/* 乘法哈希 */
int mulHash(string key) {
    long long hash = 0;
    const int MODULUS = 1000000007;
    for (unsigned char c : key) {
        hash = (31 * hash + (int)c) % MODULUS;
    }
    return (int)hash;
}

/* 异或哈希 */
int xorHash(string key) {
    int hash = 0;
    const int MODULUS = 1000000007;
    for (unsigned char c : key) {
        hash ^= (int)c;
    }
    return hash & MODULUS;
}

/* 旋转哈希 */
int rotHash(string key) {
    long long hash = 0;
    const int MODULUS = 1000000007;
    for (unsigned char c : key) {
        hash = ((hash << 4) ^ (hash >> 28) ^ (int)c) % MODULUS;
    }
    return (int)hash;
}

```cpp
/* 回溯算法框架 */
void backtrack(State *state, vector<Choice *> &choices, vector<State *> &res) {
    // 判断是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
        // 不再继续搜索
        return;
    }
    // 遍历所有选择
    for (Choice choice : choices) {
        // 剪枝：判断选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            backtrack(state, choices, res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}
/* 判断当前状态是否为解 */
bool isSolution(vector<TreeNode *> &state) {
    return !state.empty() && state.back()->val == 7;
}

/* 记录解 */
void recordSolution(vector<TreeNode *> &state, vector<vector<TreeNode *>> &res) {
    res.push_back(state);
}

/* 判断在当前状态下，该选择是否合法 */
bool isValid(vector<TreeNode *> &state, TreeNode *choice) {
    return choice != nullptr && choice->val != 3;
}

/* 更新状态 */
void makeChoice(vector<TreeNode *> &state, TreeNode *choice) {
    state.push_back(choice);
}

/* 恢复状态 */
void undoChoice(vector<TreeNode *> &state, TreeNode *choice) {
    state.pop_back();
}

/* 回溯算法：例题三 */
void backtrack(vector<TreeNode *> &state, vector<TreeNode *> &choices, vector<vector<TreeNode *>> &res) {
    // 检查是否为解
    if (isSolution(state)) {
        // 记录解
        recordSolution(state, res);
    }
    // 遍历所有选择
    for (TreeNode *choice : choices) {
        // 剪枝：检查选择是否合法
        if (isValid(state, choice)) {
            // 尝试：做出选择，更新状态
            makeChoice(state, choice);
            // 进行下一轮选择
            vector<TreeNode *> nextChoices{choice->left, choice->right};
            backtrack(state, nextChoices, res);
            // 回退：撤销选择，恢复到之前的状态
            undoChoice(state, choice);
        }
    }
}