图上进阶算法初探

Junly_JYukio · 2025-11-12 08:35:50 · 算法·理论

省流：LCA，树上差分，重链剖分，差分约束，tarjan，2 - SAT，二分图基础，基环树。

放在前面

本文并非“图论进阶算法教程”，仅用于快速记忆图论核心进阶算法的基础原理、实现逻辑与实用性。

图论作为信息学竞赛的核心板块，贯穿路径查询、约束求解、匹配优化等各类问题，从简单的树结构到复杂的有向图，都需要针对性算法突破效率瓶颈。

本文总结的算法均围绕“图的结构特性”展开：树上问题侧重“祖先关系”与“路径拆分”，有向图问题聚焦“强连通性”与“约束转化”，特殊图（二分图、基环树）则针对其独特结构设计优化方案。通过具体例题理解算法适配场景，是掌握图论的关键。

前置知识：图的邻接表存储、二分与倍增思想、BFS / DFS、并查集、线段树基础、最短路，MST。

最近公共祖先、树上前缀和、树上差分

Ⅰ. 最近公共祖先

对于一棵有根树，如果以 x 为根的子树中同时含有 a,b 两点，则称 x 是 a,b 的公共祖先。点对 (a,b) 的公共祖先集合中，定义深度最小的为 (a,b) 的最近公共祖先，记作 \textrm{LCA}(a,b)。

明显有以下性质：

3. 链 A \to B 可以拆分为 A \to \textrm{LCA}(A,B) 和 B \to \textrm{LCA}(A,B)。

因此，求出树中两点的最近公共祖先就显得尤为重要。

板子：最近公共祖先。

给定一棵有根树，请回答 m 次询问，每次询问输出给定点对 (a,b) 的最近公共祖先。

• 向上标记法

一遍深搜处理出所有节点的父节点以及深度，然后对于每一次询问，先把更深的节点往上跳到与另一个节点一样的深度，然后再一起一步一步往上跳，直到跳到同一个点，这个点就是它们的 LCA。

显然最坏时间复杂度出现在链上，为 \mathcal{O}(n)。

• 树上倍增法

如果一次不止跳一步，也许速度会更快。因此，倍增法能更加成功地处理 LCA。

考虑预处理出每个节点的深度和祖先关系。

定义 f_{i,j} 表示从 i 号点往上跳 2^j 步后的节点（如果跳不动就认为是根节点）。在祖先的祖先关系都处理好之后，子节点跳 2^j 步的结果其实就相当于其 2^{j-1} 级组先跳 2^{j-1} 步的结果，直接在递归前 \mathcal{O}(\log n) 处理即可。显然一次预处理的时间复杂度是 \mathcal{O}(n \times \log n)。

inline void dfs(int x,int fa){
    dep[x]=dep[fa]+1;
    f[x][0]=fa;
    for(int i=1; i<=20; i++) f[x][i]=f[f[x][i-1]][i-1];
    for(int i=0; i<v[x].size(); i++){
        int y=v[x][i];
        if(y==fa) continue;
        dfs(y,x);
    }
}

接下来在跳动的时候就可以直接跳 2^i 步了。按照倍增思想，做法如下：

• 要求 A 和 B 的最大公共祖先，首先要找出最深的那个，考虑放在 A 处。
• 将深度大的往上跳，所以倒序枚举 i，若深度仍然小于 B 就跳 2^i 步。
• 一起跳。排除跳多的情况即 A=B，最后 A 的父亲就是 \textrm{LCA}(A,B)。

时间复杂度 \mathcal{O}(\log n)。

inline int lca(int a,int b){
    if(dep[a]<dep[b]) swap(a,b);
    for(int i=20; i>=0; i--){
        if(dep[f[a][i]]>=dep[b]) a=f[a][i];
    }
    if(a==b) return a;
    for(int i=20; i>=0; i--){
        if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];
    }
    return f[a][0];
}

使用预处理 + 每次查询 \log 优化，总时间复杂度就变为了 \mathcal{O}((n+m) \times \log n)。

:::success[代码]{close}

#include<cstdio>
#include<vector>
int s;
char ch;
inline int read() {
    s=0;
    while((ch=getchar())<48);
    do s=(s<<3)+(s<<1)+(ch^48);
    while((ch=getchar())>47);
    return s;
}
inline void write(int x) {
    if(x>9) write(x/10);
    putchar(x%10+48);
}
std::vector<int> v[500005];
int n,m,a,b,dep[500005],f[500005][21],dis,qa,root,itemc;
inline void dfs(int x,int fa){
    dep[x]=dep[fa]+1;
    f[x][0]=fa;
    for(int i=1; i<=20; i++) f[x][i]=f[f[x][i-1]][i-1];
    for(int i=0; i<v[x].size(); i++){
        int y=v[x][i];
        if(y==fa) continue;
        dfs(y,x);
    }
}
inline int lca(int a,int b){
    if(dep[a]<dep[b]){
        itemc=a;
        a=b;
        b=itemc;
    }
    for(int i=20; i>=0; i--){
        if(dep[f[a][i]]>=dep[b]) a=f[a][i];
    }
    if(a==b) return a;
    for(int i=20; i>=0; i--){
        if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];
    }
    return f[a][0];
}
int main() {
    n=read();
    m=read();
    root=read();
    for(int i=1; i<n; i++){
        a=read(), b=read();
        v[a].push_back(b);
        v[b].push_back(a); 
    } 
    dfs(root,0);
    while(m--){
        qa=read();
        write(lca(qa,read()));
        putchar('\n');
    } 
    return 0;
}

:::

Ⅱ. 最近公共祖先所具有的性质

• 结合律

• LCA 求路径

• 三点最短路

点 x 使得 \textrm{dis}(a,x)+\textrm{dis}(b,x)+\textrm{dis}(c,x) 最小，则 x 一定是 \textrm{LCA}(a,b), \textrm{LCA}(b,c), \textrm{LCA}(a,c) 中深度最深的那个。

• 判断一点 C 是否经过路径 A \to B

若经过，则必须满足其中的至少一个条件：

其中 \oplus 表示异或。

• 判断路径 a \to b 和 c \to d 是否相交

若相交，则必定满足其中的至少一个条件：

Ⅲ. 树上差分

树上差分是“线性差分”在树结构的延伸，核心用于 批量修改路径权值（如路径加值、统计覆盖次数），并通过一次后序遍历快速得到最终结果。其本质是“将路径修改转化为端点修改”，利用树的父子继承关系，避免暴力遍历路径，时间复杂度优化至 \mathcal{O}(n \log n + q)（q 为修改次数）。

根据修改对象，树上差分分为 点差分（修改节点权值）和 边差分（修改边权值），核心均依赖 LCA 拆分路径。

1. 点差分（节点路径修改）

适用于“对路径 a \to b 上所有节点加 k”的批量操作，最终通过前缀和还原每个节点的实际值。

核心修改规则

将路径 a \to b 拆分为 a \to \text{LCA} 和 b \to \text{LCA}，通过差分数组 \text{diff}_v[] 标记端点：

结果还原（后序遍历前缀和）

修改完成后，通过一次后序 DFS 计算前缀和，得到每个节点的最终权值：

对节点 u，其最终权值 w_{\text{final}}[u] = \text{diff}_v[u] + \sum\limits_{v \in \text{son}(u)} w_{\text{final}}[v]。\ （子节点的差分影响会向上传递，覆盖整个路径）

2. 边差分（边路径修改）

树的边可唯一对应一个子节点（如边 u \to v 若 u 是父节点，则该边记为“边 v”），因此边差分可转化为子节点的差分操作。

核心修改规则

对路径 a \to b 上所有边加 k，差分数组 \text{diff}_e[] 标记规则：

结果还原（后序遍历前缀和）

边的最终权值通过后序 DFS 传递，每个子节点的差分影响对应其依附的边：

对节点 v（对应边 v），其最终边权 w_{\text{final}}[v] = \text{diff}_e[v] + \sum_{u \in \text{son}(v)} w_{\text{final}}[u]。

应用场景

• 点差分：统计多条路径覆盖的节点最大覆盖次数、节点权值的批量更新与单点查询。
• 边差分：统计多条路径覆盖的边次数、边权的批量更新与查询（如判断某边是否被所有路径覆盖）。

Ⅳ. 三者关联与核心思想

• LCA 是基础：树上前缀和的路径和计算、树上差分的路径拆分，均依赖 LCA 确定路径的公共部分，避免暴力遍历。
• 前缀和是“查询优化”：将路径和查询从 \mathcal{O}(n) 降至 \mathcal{O}(\log n)，核心是“预处理累积值”。
• 差分是“修改优化”：将路径修改从 \mathcal{O}(n) 降至 \mathcal{O}(1)（单次修改），核心是“端点标记 + 后序还原”。

三者结合可解决绝大多数树上路径相关问题，是图论中树结构的核心工具组合。

重链剖分

Ⅰ. 重链剖分基础

树链剖分用于将树分割成若干条链的形式，以维护树上路径的信息。

具体来说，将整棵树剖分为若干条链，使它组合成线性结构，然后用其他的数据结构维护信息。

重链剖分是如何将树分为不超过 \mathcal{O}(\log n) 条链条的呢？首先，上定义。

对于一棵树，

• 对于非叶子节点，重子节点表示其子节点中子树最大的子结点中编号最小的那个。
• 定义轻子节点表示剩余的所有子结点。
• 从这个结点到重子节点的边为重边。
• 到其他轻子节点的边为轻边。
• 若干条首尾衔接的重边构成重链。
• 把落单的结点也当作重链，那么整棵树就被剖分成若干条重链。

好了，比如说看下下面这棵树的剖分方式：

这个时候，姑且将代码实现放在一边，先看树的 \textrm{dfn} 序产生的无与伦比的两个关键性质：

• 一条重链上的 \textrm{dfn} 序连续；
• 一棵子树上的 \textrm{dfn} 序也连续。

这意味着，如果要处理树上的子树信息和链条信息，树链剖分绝对是专业对口的。不仅如此，因为 \textrm{dfn} 序连续的特性，还可以考虑用特殊的数据结构优化。

例如，权值树状数组和值域线段树。

而预处理出一堆树链，所需要的操作很简单 —— 是两次 dfs。

第一次 dfs，所求即为 x 的深度、子树大小、重儿子编号和父节点编号。这很简单。

第二次 dfs，在知道了重儿子编号的基础上，我们可以迅速求出许多更有用的信息，譬如这条重链的顶点，就可以在接下来的代码中一次跳很多格。而其任务简化后非常明确：求出任意节点 x 的所在重链顶点，和 \textrm{dfn} 序。

inline void dfs(int x,int f) {
    a[x].fa=f,a[x].sz=1,a[x].dep=a[f].dep+1,a[x].son=-1;
    int maxn=-1; // 代表当前最大的子树大小
    for(int i=0; i<vec[x].size(); i++) {
        int y=vec[x][i];
        if(y==f) continue;
        dfs(y,x);
        a[x].sz+=a[y].sz;
        if(a[y].sz>maxn) {
            maxn=a[y].sz;
            a[x].son=y;
        }
    }
}
inline void get(int x,int num) { // 此处的 num 是当前 x 所在重链的顶端节点
    a[x].top=num,a[x].dfn=++idy; // 更新顶端
    rnk[idy]=x;
    if(a[x].son==-1) return;
    get(a[x].son,num);
    for(int i=0; i<vec[x].size(); i++) {
        int y=vec[x][i];
        if(y==a[x].fa or y==a[x].son) continue;
        get(y,y);
    }
}

这么做，还产生了更多巧妙的性质，在做题的时候就可以加以应用了。

• 树上每个节点都属于且仅属于一条重链。
• 所有的重链将整棵树完全剖分。
• 在剖分时重边优先遍历，最后树的 DFS 序上，重链内的 DFS 序是连续的。按 DFN 排序后的序列即为剖分后的链。

因此，对于树上的任意一条路径，把它拆分成从 LCA 分别向两边往下走，分别最多走 \mathcal{O}(\log n) 次，因此，树上的每条路径都可以被拆分成不超过 \mathcal{O} (\log n) 条重链。加上重链上连续序号的性质，我们便能迅速维护链上信息。

Ⅱ. 重链剖分的应用

板子题：应用重链剖分。

重链剖分的核心价值的是利用 \textrm{dfn} 序“连续”的特性，将树的路径、子树转化为线性区间，再结合线段树、树状数组等数据结构，高效处理 路径查询/修改、子树查询/修改 两类核心问题。其应用均围绕“跳重链”思想展开，单次操作时间复杂度为 \mathcal{O}(\log^2 n)（含数据结构操作），能适配大规模数据场景。

1. 求最近公共祖先（LCA）

重链剖分可独立实现 LCA 求解，核心逻辑是“跳重链至同一条链”，步骤简洁且效率稳定。

• 核心原理：两点向上跳重链时，优先跳顶端深度更大的链，直到两点处于同一条重链；此时深度较小的节点即为 LCA。
• 实现代码：

inline int lca(int u,int v) {
    while(arr[u].top!=arr[v].top) {
        if(arr[arr[u].top].dep<arr[arr[v].top].dep)swap(u,v);
        u=arr[arr[u].top].f;
    }
    return arr[u].dep<arr[v].dep ? u : v;
}

• 优势：无需额外预处理倍增数组，与剖分过程自然融合，代码复用性高。

2. 路径信息维护

适用于“路径区间加值、路径区间求和/最大值/最小值”等操作，核心是将路径拆分为若干条重链，通过数据结构批量处理连续区间。

• 核心步骤：
  1. 若两点不在同一条重链，先处理顶端深度更大的链（区间为顶端 \textrm{dfn} 至当前节点 \textrm{dfn}）；
  2. 两点跳至同一条重链后，处理剩余区间（深度较小节点 \textrm{dfn} 至深度较大节点 \textrm{dfn}）；
  3. 结合线段树 / 树状数组完成区间修改或查询。
• 典型操作代码： 路径区间加值（结合线段树）：

inline void update_path(int x,int y,int k) {
    while(arr[x].top!=arr[y].top) {
        if(arr[arr[x].top].dep<arr[arr[y].top].dep)swap(x,y);
        modify(1,1,n,arr[arr[x].top].dfn,arr[x].dfn,k);
        x=arr[arr[x].top].f;
    }
    if(arr[x].dep>arr[y].dep)swap(x,y);
    modify(1,1,n,arr[x].dfn,arr[y].dfn,k);
}

路径区间求和（结合线段树）：

inline int query_path(int x,int y) {
    int res=0;
    while(arr[x].top!=arr[y].top) {
        if(arr[arr[x].top].dep<arr[arr[y].top].dep)swap(x,y);
        res=(res+query(1,1,n,arr[arr[x].top].dfn,arr[x].dfn))% Mod;
        x=arr[arr[x].top].f;
    }
    if(arr[x].dep>arr[y].dep)swap(x,y);
    return(res+query(1,1,n,arr[x].dfn,arr[y].dfn))% Mod;
}

3. 子树信息维护

由于子树的 \textrm{dfn} 序连续（区间为 \text{dfn}[u] \sim \text{dfn}[u] + \text{sz}[u] - 1），可直接通过数据结构完成子树的批量修改与查询。

• 核心原理：子树大小 \text{sz}[u] 决定了子树对应的 \textrm{dfn} 区间长度，无需跳重链，直接定位区间即可。
• 典型操作代码：\ 子树区间加值：

inline void update_subtree(int u,int k) {
    modify(1,1,n,arr[u].dfn,arr[u].dfn+arr[u].sz-1,k);
}

子树区间求和：

inline int query_subtree(int u) {
    return query(1,1,n,arr[u].dfn,arr[u].dfn+arr[u].sz-1)%Mod;
}

这份代码适配“路径加、路径查、子树加、子树查”四类操作，是重链剖分的经典应用模板。

:::success[代码]{close}

#include<cstdio>
int s;
char ch;
inline int read() {
    s=0;
    while((ch=getchar_unlocked())<48);
    do s=(s<<3)+(s<<1)+(ch^48);
    while((ch=getchar_unlocked())>47);
    return s;
}
inline void write(int x) {
    if(x>9) write(x/10);
    putchar(x%10+48);
}
struct node {
    int val,dfn,f,sz,dep,hson,top;
} arr[100002];
int n,T,root,Mod,fr,to,num,rnk[100002];
long long sum[400002],tag[400002];
int head[100002],ver[200002],ne[200002],tot,item;
inline void add(int x,int y) {
    ver[++tot]=y;
    ne[tot]=head[x];
    head[x]=tot;
}
inline void dfs_first(int x,int fa) {
    arr[x].f=fa;
    arr[x].dep=arr[fa].dep+1;
    arr[x].sz=1;
    int max_size=-1;
    for(int i=head[x]; i; i=ne[i]) {
        int y=ver[i];
        if(y==fa) continue;
        dfs_first(y,x);
        arr[x].sz+=arr[y].sz;
        if(arr[y].sz>max_size) {
            max_size=arr[y].sz;
            arr[x].hson=y;
        }
    }
}
inline void dfs_second(int x,int now_top) {
    arr[x].dfn=++num;
    rnk[num]=arr[x].val;
    arr[x].top=now_top;
    if(!arr[x].hson) return;
    dfs_second(arr[x].hson,now_top);
    for(int i=head[x]; i; i=ne[i]) {
        int y=ver[i];
        if(y==arr[x].f or y==arr[x].hson) continue;
        dfs_second(y,y);
    }
}
inline void build(int p,int l,int r) {
    tag[p]=0;
    if(l==r) {
        sum[p]=rnk[l];
        return;
    }
    int mid=l+r>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
    sum[p]=(sum[p<<1]+sum[p<<1|1])%Mod;
}
inline void pushdown(int p,int l,int r) {
    if(!tag[p]) return;
    int lc=p<<1,rc=p<<1|1,mid=l+r>>1;
    tag[lc]=(tag[lc]+tag[p])%Mod;
    tag[rc]=(tag[rc]+tag[p])%Mod;
    sum[lc]=(sum[lc]+(tag[p]*(mid-l+1))%Mod)%Mod;
    sum[rc]=(sum[rc]+(tag[p]*(r-mid))%Mod)%Mod;
    tag[p]=0;
}
inline void modify(int p,int l,int r,int s,int t,int cc) {
    if(s<=l and r<=t) {
        sum[p]=(sum[p]+(cc*(r-l+1))%Mod)%Mod;
        tag[p]=(tag[p]+cc)%Mod;
        return;
    }
    pushdown(p,l,r);
    int mid=l+r>>1;
    if(s<=mid) modify(p<<1,l,mid,s,t,cc);
    if(t>mid) modify(p<<1|1,mid+1,r,s,t,cc);
    sum[p]=(sum[p<<1]+sum[p<<1|1])%Mod;
}
inline long long query(int p,int l,int r,int s,int t) {
    if(s<=l and r<=t) return sum[p];
    pushdown(p,l,r);
    int mid=l+r>>1;
    long long result=0;
    if(s<=mid) result=query(p<<1,l,mid,s,t);
    if(t>mid) result=(result+query(p<<1|1,mid+1,r,s,t))%Mod;
    return result;
}
inline void update(int x,int y,int k) {
    while(arr[x].top!=arr[y].top) {
        if(arr[arr[x].top].dep<arr[arr[y].top].dep) {item=x;x=y;y=item;}
        modify(1,1,n,arr[arr[x].top].dfn,arr[x].dfn,k);
        x=arr[arr[x].top].f;
    }
    if(arr[x].dep>arr[y].dep) {item=x;x=y;y=item;}
    modify(1,1,n,arr[x].dfn,arr[y].dfn,k);
}
inline int ask(int x,int y) {
    int ans=0;
    while(arr[x].top!=arr[y].top) {
        if(arr[arr[x].top].dep<arr[arr[y].top].dep) {item=x;x=y;y=item;}
        ans=(ans+query(1,1,n,arr[arr[x].top].dfn,arr[x].dfn))%Mod;
        x=arr[arr[x].top].f;
    }
    if(arr[x].dep>arr[y].dep) {item=x;x=y;y=item;}
    return (ans+query(1,1,n,arr[x].dfn,arr[y].dfn))%Mod;
}
int opt,qx,qy;
int main() {
    n=read(), T=read(), root=read(), Mod=read();
    for(int i=1; i<=n; i++) arr[i].val=read();
    for(int i=1; i<n; i++) {
        fr=read(), to=read();
        add(fr,to);
        add(to,fr);
    }
    dfs_first(root,0);
    dfs_second(root,root);
    build(1,1,n);
    while(T--) {
        opt=read(), qx=read();
        if(opt==1) {
            qy=read();
            update(qx,qy,read());
        } else if(opt==2) {
            write(ask(qx,read()));
            putchar('\n');
        } else if(opt==3) {
            modify(1,1,n,arr[qx].dfn,arr[qx].dfn+arr[qx].sz-1,read());
        } else {
            write(query(1,1,n,arr[qx].dfn,arr[qx].dfn+arr[qx].sz-1));
            putchar('\n');
        }
    }
    return 0;
}

:::

差分约束

差分约束问题通常进行在一个神秘的不等式方程组内，其往往需要协调较多的内容，如果不建模为图上信息的互相制约，恐怕很难进行处理。

差分约束系统由一组 线性不等式约束 构成，所有约束均围绕两个变量的差值与常数的关系展开。设 x_1, x_2, ..., x_n 为 n 个变量，约束的标准形式分为两类：

• 上界约束：x_i - x_j \leq c（x_i 与 x_j 的差值不超过常数 c）
• 下界约束：x_i - x_j \geq c（x_i 与 x_j 的差值不小于常数 c）

其中 c 是已知常数，i, j \in \{1, 2, ..., n\}。我们的目标是找到一组满足所有约束的变量值（可行解），或判断系统无解。

板子题。\ 该问题的基础版本是：给定 c_1 \sim s_m，你需要找出任意一组 x_1,x_2,\cdots,x_n，满足：\begin{cases} x_{c_1}-x_{c'_1}\leq y_1 \\x_{c_2}-x_{c'_2} \leq y_2 \\ \cdots\\ x_{c_m} - x_{c'_m}\leq y_m\end{cases} 若无解，请输出 NO。n,m \le 5 \times 10^3，c_i \neq c'_i。

首先，需要将该题目抽象成图上问题。差分约束的本质是“将不等式转化为路径关系”，这一转化源于最短路径 / 最长路径的松弛特性 —— 不等式的结构与路径长度的约束完全等价。

考虑上界约束 x_i - x_j \le c，对其进行等价变形，即可变为 x_i \le x_j + c。 这与图论中 最短路径的松弛条件 高度契合：

在有向图中，若存在边 j\rightarrow i，权值为 c，则节点 i 的最短路径长度 d_i 满足 d_i\leq d_j+c。

由此建立映射规则：

• 每个变量 x_k 对应图中的一个节点 k；
• 约束 x_i - x_j \leq c 对应图中一条 从 j 到 i、权值为 c 的有向边。

同理，如果要考虑下界约束 x_i-x_j \ge c，就只需要建立一条从 i 到 j 的，权值为 c 的边即可。

转化为图之后又怎么做呢？

在图中，我们发现上面的部分存在解，而下面的部分无解。

:::info[推导]{open}

代入得：\

答案绝对是中点或者中点的子树。但是，答案中不能包含被查询的点一侧的子树。

定义 c 为 a 和 b 中深度较大的那个，故答案为：

仍然可用 \mathcal{O}(\log n) 的时间复杂度处理。

综上，此题可以使用 \mathcal{O}((n+m) \times \log n) 的时间复杂度完成。

:::success[代码]{close}

#include<cstdio>
#define N 100002
char ch;
inline char gc() {
    static char buf[1<<18],*p1=buf,*p2=buf;
    if(p1==p2) {
        p2=(p1=buf)+fread(buf,1,1<<18,stdin);
        if(p1==p2) return EOF;
    }
    return *p1++;
}
template<typename _Tp>
inline void read(_Tp& x) {
    x=0;
    while((ch=gc())<48);
    do x=(x<<3)+(x<<1)+(ch^48);
    while((ch=gc())>47);
}
template<typename _Tp>
inline void write(_Tp x) {
    if(x>9) write(x/10);
    putchar((x%10)^48);
}
int head[N],ver[N<<1],ne[N<<1],tot;
inline void add(int x,int y) {
    ver[++tot]=y;
    ne[tot]=head[x], head[x]=tot;
}
int n,fr,to,m,dep[N],f[N][20],flc,dist,sz[N];
inline void dfs(int x,int fa) {
    dep[x]=dep[fa]+1;
    f[x][0]=fa;
    sz[x]=1;
    for(int i=1; i<=19; i++) f[x][i]=f[f[x][i-1]][i-1];
    for(int i=head[x]; i; i=ne[i]) {
        int y=ver[i];
        if(fa==y) continue;
        dfs(y,x);
        sz[x]+=sz[y];
    }
}
inline int lca(int x,int y) {
    if(dep[x]<dep[y]) x^=y^=x^=y;
    for(int i=19; i>=0; i--) {
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    }
    if(x==y) return x;
    for(int i=19; i>=0; i--) {
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    }
    return f[x][0];
}
inline int Jump(int x,int step) {
    for(int i=19; i>=0; i--) {
        if((1<<i)&step) x=f[x][i];
    }
    return x;
}
int main() {
    read(n);
    for(int i=1; i<n; i++) {
        read(fr), read(to);
        add(fr,to);
        add(to,fr);
    }
    dfs(1,0);
    read(m);
    while(m--) {
        read(fr), read(to);
        if(fr==to) {
            write(n),putchar('\n');
            continue;
        }
        flc=lca(fr,to);
        dist=dep[fr]+dep[to]-dep[flc]-dep[f[flc][0]];
        if(!(dist&1)){
            write(0), putchar('\n');
            continue;
        }
        if(dep[fr]==dep[to]){
            write(n-sz[Jump(fr,dist/2-1)]-sz[Jump(to,dist/2-1)]), putchar('\n');
            continue;
        }
        if(dep[fr]>dep[to]) fr^=to^=fr^=to;
        write(sz[Jump(to,dist/2)]-sz[Jump(to,dist/2-1)]), putchar('\n');
    }
    return 0;
}

:::

例题 2

link：疫情控制。

给定一棵树，根为 1，点编号 1 \sim n，带边权。令 \textrm{dis}(i,j) 为树链 i \to j 上的所有边权之和。

树上有 m 枚棋子，第 i 个棋子位于编号为 c_i 的节点。你需要将这些棋子挪动到新位置，其中第 i 个棋子移动至 d_i(d_i \neq 1)，使得在新的树中，从根节点到任意一个叶子节点的路径中，存在至少一枚棋子。

请输出：\min(\max\limits_{i=1}^{m} \textrm{dis}(c_i,d_i))。2 \le m \le n \le 5 \times 10^4，边权 0 < w < 10^9。

注意到题目所要求的 \max\limits_{i=1}^{m} \textrm{dis}(c_i,d_i) 具有单调性：即对于某个方案，其花费为 t=\max\limits_{i=1}^{m} \textrm{dis}(c_i,d_i)，则对于 \ge t 的每个方案，都一定可行，只需要在区间 [1,t-1] 去找寻答案了。

考虑二分 \textrm{now}=\max\limits_{i=1}^{m} \textrm{dis}(c_i,d_i)。如何写出 check 呢？

尝试使用贪心。首先题意可以转化为：对于每个棋子，其能将以自己为根的子树染色。最后答案也就是需要将树中所有除根之外的点都染色。这样一来，就有如下性质：

对于每个棋子，如果其父亲不是根节点，且其剩余的 \textrm{now} 能够支持其往上跳，就一定要跳至父亲。

证明很简单：其跳至父亲一定更优（能染色的节点更多），跳至子节点一定更劣（能染色的节点更少）。一个点只能跳至父亲、子节点，或原地不动，则如果能跳，就一定要跳。

但是这还不够。

如图，如果只按照“一直往上跳，直到跳不动或者跳到根”的策略来进行，就会出现问题。

程序会这么看待几次操作：

• 棋子 A：4 \to 3 \to 2，需要花费：9。
• 棋子 B：9 \to 8 \to 2，需要花费：5。
• 棋子 C：18 \to 17 \to 16 \to 15 \to 14，需要花费：20。
• 棋子 D：原地不动。

此时需要花费的最大代价是 20。

如果这么做呢：

• 棋子 A：4 \to 3 \to 2，需要花费：9。
• 棋子 B：9 \to 8 \to 2 \to 1 \to 14，需要花费：10。
• 棋子 C：18 \to 17 \to 16，需要花费：10。
• 棋子 D：原地不动。

此时需要花费的最大代价是 10。

所以可见，一个棋子并不是移到根节点的儿子就一定停止。

因此，我们把所有走到根节点后代价仍 \le \textrm{now} 的棋子存下来，并且同时记录根节点有哪些叶子未被覆盖。

不妨把剩余可用路程更少的棋子分配给连接根节点与不合法的叶子的边的边权更小的孩子进行支援；若发现某个棋子无力支援分配给它的子树，那么这个棋子就留在自己的子树里。

此外，有余力支援其它部分的棋子，有留在自己子树的选择，此时代价为 0。

综上所述，代码需要完成以下几个步骤：

• 预处理出所有点的深度，父亲和跳跃花费的代价；
• 二分值 \textrm{now}，check 写法如下：
  • 使用类似于 LCA 的倍增法跳到自己力所能及的位置，如果能调到根节点的儿子就记录；
  • 对于记录的棋子，不妨将根节点至所有儿子的边进行排序，而后又根据贪心思想，将所有可动棋子都移至根节点，并将这些点能走的剩余路径进行排序。显然，能走的最远的棋子应该去处理最远的儿子节点。

此题可 A。

:::success[代码]{close}

#include<cstdio>
#include<algorithm>
#define N 50002
#define int long long
using std::sort;
char ch;
inline char gc() {
    static char buf[1<<18],*p1=buf,*p2=buf;
    if(p1==p2) {
        p2=(p1=buf)+fread(buf,1,1<<18,stdin);
        if(p1==p2) return EOF;
    }
    return *p1++;
}
template<typename _Tp>
inline void read(_Tp& x) {
    x=0;
    while((ch=gc())<48);
    do x=(x<<3)+(x<<1)+(ch^48);
    while((ch=gc())>47);
}
int n,m,tot,fr,to,wi,l,r,mid,ans=-1,a[N],head[N],ver[N<<1],ne[N<<1],wei[N<<1],f[N][16],g[N][16];
bool vis[N];
struct data {
    int wei,id;
    bool operator < (const data &tool) const {
        return wei<tool.wei;
    }
} chess[N],bin[N];
inline void add(int x,int y,int w) {
    ver[++tot]=y,wei[tot]=w;
    ne[tot]=head[x],head[x]=tot;
}
inline void dfs(int x,int fa) {
    for(int j=1; j<=15; j++) {
        f[x][j]=f[f[x][j-1]][j-1];
        g[x][j]=g[x][j-1]+g[f[x][j-1]][j-1];
    }
    for(int i=head[x]; i; i=ne[i]) {
        int y=ver[i];
        if(y==fa) continue;
        f[y][0]=x;
        g[y][0]=wei[i];
        dfs(y,x);
    }
}
inline void putTag(int u,int fa) {
    bool res=1,flg=0;
    for(int i=head[u]; i; i=ne[i]) {
        int v=ver[i];
        if(v^fa) putTag(v,u),res&=vis[v],flg=1;
    }
    if(u!=1 and res and flg) vis[u]=1;
}
inline bool check(int lim) {
    for(int i=1; i<=n; i++) vis[i]=0;
    int flc=0,clf=0;
    for(int i=1; i<=m; i++) {
        int x=a[i],sum=0;
        for(int j=15; j>=0; j--) if(f[x][j]>1 and sum+g[x][j]<=lim) sum+=g[x][j],x=f[x][j];
        if(f[x][0]==1 and sum+g[x][0]<=lim) chess[++flc]=data {lim-sum-g[x][0],x};
        else vis[x]=1;
    }
    putTag(1,0);
    for(int i=head[1]; i; i=ne[i]) {
        int v=ver[i];
        if(!vis[v]) bin[++clf]=data {wei[i],v};
    }
    sort(chess+1,chess+flc+1);
    sort(bin+1,bin+clf+1);
    int pos=1;
    for(int i=1; i<=flc; i++) {
        if(!vis[chess[i].id]) vis[chess[i].id]=1;
        else if(chess[i].wei>=bin[pos].wei) vis[bin[pos].id]=1;
        while(vis[bin[pos].id] and pos<=clf) pos++;
    }
    return pos>clf;
}
signed main() {
    read(n);
    for(int i=1; i<n; i++) {
        read(fr), read(to), read(wi);
        add(fr,to,wi),add(to,fr,wi);
        r+=wi;
    }
    dfs(1,0);
    read(m);
    for(int i=1; i<=m; i++) read(a[i]);
    while(l<=r) {
        mid=(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    printf("%lld",ans);
    return 0;
}

:::

例题 3

link：Max Flow P

有 n 个节点的树，q 次操作，每次将路径 a \to b 上的所有点权加 1，求最终最大的点权。2 \le n \le 5 \times 10^4，1 \le q \le 10^5。

学了前面的东西，这就是一道板中板题目。

1. 预处理 LCA 的倍增数组和节点深度。
2. 对每次操作，执行点差分修改。
3. 后序遍历计算前缀和，还原每个节点的最终权值，记录最大值。

:::success[代码]{close}

#include<cstdio>
int s; 
char ch;
inline int read(){
    s=0;
    while((ch=getchar_unlocked())<48);
    do s=(s<<3)+(s<<1)+(ch^48);
    while((ch=getchar_unlocked())>47);
    return s;
}
int n,k,item,head[500002],ver[1000002],ne[1000002],tot,maxn,d[500002],dep[500002],f[500002][25],x,y;
inline void add(int x,int y) {
    ver[++tot]=y;
    ne[tot]=head[x],head[x]=tot;
}
inline void dfs(int x,int fa) {
    dep[x]=dep[fa]+1;
    f[x][0]=fa;
    for(int i=1; i<=20; i++) f[x][i]=f[f[x][i-1]][i-1];
    for(int i=head[x]; i; i=ne[i]) {
        int y=ver[i];
        if(y==fa) continue;
        dfs(y,x);
    }
}
inline int lca(int x,int y) {
    if(dep[x]<dep[y]) {item=x;x=y;y=item;}
    for(int i=20; i>=0; i--) {
        if(dep[f[x][i]]>=dep[y]) x=f[x][i];
    }
    if(x==y) return x;
    for(int i=20; i>=0; i--) {
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    }
    return f[x][0];
}
inline void dfs2(int x,int fa) {
    for(int i=head[x]; i; i=ne[i]) {
        int y=ver[i];
        if(y==fa) continue;
        dfs2(y,x);
        d[x]+=d[y];
    }
    maxn=(maxn>d[x])?maxn:d[x];
}
int main() {
    n=read(), k=read();
    for(int i=1; i<n; i++) {
        x=read(), y=read();
        add(x,y), add(y,x);
    }
    dfs(1,0);
    while(k--) {
        x=read(), y=read();
        int p=lca(x,y);
        d[x]++,d[y]++;
        d[p]--,d[f[p][0]]--;
    }
    dfs2(1,0);
    printf("%d",maxn); 
    return 0;
}

:::

例题 4

link：小 K 的农场。

有 n 个农场，给你 m 条约束信息，如下：

• 农场 a 比农场 b 至少多种植了 c 个单位的作物；
• 农场 a 比农场 b 至多多种植了 c 个单位的作物；
• 农场 a 与农场 b 种植的作物数一样多。

问是否存在合法的农场作物分配满足所有约束条件。

简单差分约束题。其中，“至少多”和“至多多”明显可以直接用建边法来做；

农场 a 比农场 b 至少多种植了 c 个单位的作物代表 a-b \ge c，可以表示为 b \to a，权值为 -c。

而农场 a 比农场 b 至少多种植了 c 个单位的作物代表 a-b \le c，可以表示为 a \to b，权值为 c。

至于“相等”，则可以建一条双向边，两条权值均为 0，因为若 a \le b，b \le a，则 a=b。在判断负环后，输出 No(有负环) 或者 Yes(没负环) 即可。

此题可解。

:::success[代码]{close}

#include<bits/stdc++.h>
#define F first
#define S second
#define PII pair<int,int>
using namespace std;
char ch;
inline char gc() {
    static char buf[1<<18],*p1=buf,*p2=buf;
    if(p1==p2) {
        p2=(p1=buf)+fread(buf,1,1<<18,stdin);
        if(p1==p2) return EOF;
    }
    return *p1++;
}
int f;
template<typename _Tp>
inline void read(_Tp& x) {
    x=0, f=1;
    do if(ch=='-') f=-1;
    while((ch=gc())<48);
    do x=(x<<3)+(x<<1)+(ch^48);
    while((ch=gc())>47);
    x*=f;
}
template<typename _Tp>
inline void write(_Tp x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar((x%10)^48);
}
vector<PII> vec[5002];
int n,m,fr,to,wi,dis[5002],op;
bool bell;
int main() {
    read(n), read(m);
    for(int i=1; i<=m; i++) {
        read(op);
        if(op==1){
            read(fr), read(to), read(wi);
            vec[to].push_back({fr,-wi});
        }else if(op==2){
            read(fr), read(to), read(wi);
            vec[fr].push_back({to,wi});
        }else{
            read(fr), read(to);
            vec[to].push_back({fr,0});
            vec[fr].push_back({to,0});
        }
    }
    for(int i=1; i<=n; i++) vec[0].push_back({i,0}),dis[i]=2e9;
    dis[0]=0;
    for(int i=1; i<=n; i++) {
        bell=0;
        for(int j=0; j<=n; j++) {
            if(dis[j]==2e9) continue;
            for(PII k:vec[j]) if(dis[k.F]>dis[j]+k.S) {
                    dis[k.F]=dis[j]+k.S;
                    bell=1;
                }
        }
        if(!bell) break;
    }
    bell=0;
    for(int j=1; j<=n; j++) {
        if(dis[j]==2e9) continue;
        for(PII k:vec[j]) if(dis[k.F]>dis[j]+k.S) {
                dis[k.F]=dis[j]+k.S;
                bell=1;
            }
        if(bell) break;
    }
    if(bell){
        puts("No");
        return 0;
    }
    puts("Yes");
    return 0;
}

:::

练习题

例题 5

link：Grass Cownoisseur G。

考虑分层图。在缩点后，对于“只逆行一次”的处理方案可以设两层图，第一层图和第二层图之间靠反边连结。此题可解。

:::success[代码]{close}

#include<cstdio>
#include<vector>
#include<queue>
char ch;
inline char gc() {
    static char buf[1<<18],*p1=buf,*p2=buf;
    if(p1==p2) {
        p2=(p1=buf)+fread(buf,1,1<<18,stdin);
        if(p1==p2) return EOF;
    }
    return *p1++;
}
int s;
inline int read(){
    s=0;
    while((ch=gc())<48);
    do s=(s<<3)+(s<<1)+(ch^48);
    while((ch=gc())>47);
    return s;
}
std::vector<int> vec[300002];
int n,m,head[100002],ver[100002],ne[100002],tot,fr,to,fx,fy,dist[200002];
inline void add(int x){
    ver[++tot]=read();
    ne[tot]=head[x], head[x]=tot;
} 
int dfn[100002],low[100002],st[100002],top,num,z,cnt,scc[100002],sz[200002],tag[200002];
bool vis[100002];
void tarjan(int x){
    dfn[x]=low[x]=++num;
    vis[x]=1,st[++top]=x;
    for(int i=head[x]; i; i=ne[i]){
        int y=ver[i];
        if(!dfn[y]){
            tarjan(y);
            if(low[y]<low[x]) low[x]=low[y];
        }else if(vis[y] and dfn[y]<low[x]) low[x]=dfn[y];
    }
    if(dfn[x]==low[x]){ // 当前点 x 是一个新的堆的开头 
        cnt++;
        while(true){
            z=st[top--];
            scc[z]=cnt;
            sz[cnt]++;
            vis[z]=0;
            if(x==z) break;
        }
    }
} 
int main(){
    n=read(), m=read();
    for(int i=1; i<=m; i++) add(read());
    for(int i=1; i<=n; i++) if(!dfn[i]) tarjan(i);
    if(cnt==1){
        printf("%d",n);
        return 0;
    }
    // 构建第二层图结构 
    for(int x=1; x<=n; x++){
        fx=scc[x];
        for(int i=head[x]; i; i=ne[i]){
            fy=scc[ver[i]];
            if(fx==fy) continue;
            // 警示后人:是 cnt 不是 n 
            vec[fx].push_back(fy); // 正常建边
            vec[fy].push_back(fx+cnt); // 在第二层和第一层里建边
            vec[fx+cnt].push_back(fy+cnt); // 在第二层开建 
        }
    }
    for(int i=1; i<=cnt; i++) sz[i+cnt]=sz[i]; // 复制权值 
    // 使用 SPFA 跑最短路 
    std::queue<int> qu;
    qu.push(scc[1]); // 警示后人：是 scc[1] 不是 1 
    tag[scc[1]]=1;
    while(!qu.empty()){
        int x=qu.front();
        qu.pop();
        tag[x]=0;
        for(int i=0; i<vec[x].size(); i++){
            int y=vec[x][i];
            if(dist[y]<dist[x]+sz[y]){
                dist[y]=dist[x]+sz[y];
                if(!tag[y]){
                    tag[y]=1;
                    qu.push(y);
                }
            }
        }
    }
    printf("%d",dist[scc[1]+cnt]);
    return 0;
}

:::

例题 6

link：Knights Of The Round Table。

首先，我们知道点双连通分量由一堆环组成。

假设在点双连通分量之中有环 a ，若 a 是奇环，那么 a 中所有点都可以开会，不影响答案。

若 a 是偶环，那么将它和点双中的奇环链接成一个大奇环就可以了。

诶，那这简单了。

先建补图，补图上 Tarjan 求点双，对于每一个点双二分图染色判断是否有奇环，不在任何一个有奇环的点双上的点都无法参加会议。

此题可解。

:::success[代码]{close}

#include<cstdio>
int s;
char ch;
inline int read(){
    s=0;
    while((ch=getchar())<48);
    do s=(s<<3)+(s<<1)+(ch^48);
    while((ch=getchar())>47);
    return s;
}
inline void write(int x){
    if(x>9) write(x/10);
    putchar(x%10+48);
}
int head[1002],ver[2000005],ne[2000005],tot;
inline void add(int x,int y){
    ver[++tot]=y;
    ne[tot]=head[x],head[x]=tot;
}
int n,m,p[1002][1002],fr,to;
inline void solve(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++) p[i][j]=0;
    }
    m=read();
    for(int i=1; i<=m; i++){
        fr=read(), to=read();
        p[fr][to]=p[fr][to]=1;
    }
    for(int i=1; i<=n; i++){
        for(int j=i+1; j<=n; j++) if(!p[i][j]) add(i,j),add(j,i);
    }
    for(int i=1; i<=n; i++){
        if(!dfn[i]){

        }
    }
}
int main(){
    while(n=read()) solve();
    return 0;
}

:::

例题 7

link：银河。

差分约束。但是此题还需要求最小值。

考虑 SCC 缩点法。在缩点之后，所有可以相等的值成为一个强连通分量。再在小图上作拓扑排序，此题可解。

:::success[代码]{close}

#include<cstdio>
#include<vector>
#include<queue>
int s;
char ch;
inline int read() {
    s=0;
    while((ch=getchar())<48);
    do s=(s<<3)+(s<<1)+(ch^48);
    while((ch=getchar())>47);
    return s;
}
int head[100002],ne[200002],ver[200002],w[200002],tot;
inline void add(int x,int y,int z) {
    ver[++tot]=y, w[tot]=z;
    ne[tot]=head[x], head[x]=tot;
}
int n,m,t,a,b,du[100002],dfn[100002],low[100002],st[100002],scc[100002],sz[100002],dis[100002],top,num,cnt,z,fx;
long long ans;
bool vis[100002];
std::vector<int> vec[100002],wec[100002];
inline void tarjan(int x) {
    dfn[x]=low[x]=++num;
    st[++top]=x, vis[x]=1;
    for(int i=head[x]; i; i=ne[i]) {
        int y=ver[i];
        if(!dfn[y]) {
            tarjan(y);
            if(low[y]<low[x]) low[x]=low[y];
        } else if(vis[y] and dfn[y]<low[x]) low[x]=dfn[y];
    }
    if(low[x]==dfn[x]) {
        cnt++;
        while(true) {
            z=st[top--];
            scc[z]=cnt;
            vis[z]=0;
            sz[cnt]++;
            if(x==z) break;
        }
    }
}
int main() {
    n=read(), m=read();
    for(int i=1; i<=m; i++){
        t=read(), a=read(), b=read();
        if(t==1) add(a,b,0),add(b,a,0);
        else if(t==2) add(a,b,1);
        else if(t==3) add(b,a,0);
        else if(t==4) add(b,a,1);
        else if(t==5) add(a,b,0);
    }
    for(int i=1;i<=n;i++){
        if(!dfn[i])
            tarjan(i);
    }
    bool flag=0;
    for(int x=1; x<=n; x++){
        for(int i=head[x]; i; i=ne[i]){
            int y=ver[i];
            if(scc[x]==scc[y]){
                if(w[i]>0){
                    puts("-1");
                    return 0;
                }
                continue;
            }
            vec[scc[x]].push_back(scc[y]);
            wec[scc[x]].push_back(w[i]);
            du[scc[y]]++;
        }
    }

    std::queue<int> q;
    for(int i=1; i<=cnt; i++) {
        if(du[i]==0) {
            q.push(i);
            dis[i]=1;
        }
    }
    while(!q.empty()) {
        int x=q.front();
        q.pop();
        for(int i=0; i<vec[x].size(); i++) {
            int y=vec[x][i];
            du[y]--;
            if(dis[y]<dis[x]+wec[x][i]) dis[y]=dis[x]+wec[x][i];
            if(du[y]==0) q.push(y);
        }
    }
    for(int i=1; i<=cnt; i++) ans+=(long long)sz[i]*dis[i];
    printf("%lld",ans);
    return 0;
}

:::

例题 8

link：游戏。

乍眼一看，此题好像是一个 3-SAT 问题，因为在特殊赛道 x 上，存在 3 种属性值，不再是布尔变量。这样一来，貌似此题就成为了 NP-难 问题。

一种暴力的想法是枚举 x 地图不用哪一种车，将 x 地图转化为一般地图求解。这样状态总数将达到 3^d，明显无法承受。

注意到上面的枚举过程中，我们没有必要枚举所有三种普通地图，只用枚举两种地图即可。因为任意两种普通地图的组合，都能完整覆盖三种可用的车。在 \mathcal{\omega}(2^d) 的复杂度内，此题可解。

:::success[代码]{close}

#include<cstdio>
#include<string>
#define For(i,a,b) for(int i=a; i<=b; i++)
#define N 150002
#define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXSIZE,stdin),p1==p2)?EOF:*p1++)
constexpr int MAXSIZE=2e5;
char buf[MAXSIZE],*p1,*p2;
inline char getc() {
    char c=gc();
    while(c>'Z' or c<'A')c=gc();
    return c;
}
inline std::string READ() {
    std::string ret="";
    char c=gc();
    while(c==' ' or c=='\n') c=gc();
    while(c!=' ' and c!='\n') ret+=c,c=gc();
    return ret;
}
inline int read() {
    int ans=0;
    char c=gc();
    while(c>'9' or c<'0') c=gc();
    while(c>='0' and c<='9') ans=(ans<<1)+(ans<<3)+(c^48),c=gc();
    return ans;
}
struct node {
    int a,x,b,y;
} a[N];
int head[N],ver[N],ne[N],tot;
inline void add(int x,int y) {
    ver[++tot]=y;
    ne[tot]=head[x], head[x]=tot;
}
std::string str;
char op;
int n,m,d,s[N][2],plc[N],cur,dfn[N],low[N],st[N],scc[N],top,z,num,cnt,h1,h2;
bool flag;
inline void tarjan(int x) {
    dfn[x]=low[x]=++num,st[++top]=x;
    for(int i=head[x]; i; i=ne[i]) {
        int y=ver[i];
        if(!dfn[y]) {
            tarjan(y);
            if(low[y]<low[x]) low[x]=low[y];
        } else if(!scc[y] and dfn[y]<low[x]) low[x]=dfn[y];
    }
    if(low[x]==dfn[x]) {
        cnt++;
        while(true) {
            z=st[top--];
            scc[z]=cnt;
            if(z==x) break;
        }
    }
}
int main() {
    n=read(), d=read();
    str=READ();
    m=read();
    For(i,1,n) {
        op=str[i-1];
        if(op=='a') s[i][0]=2,s[i][1]=3;
        else if(op=='b') s[i][0]=1,s[i][1]=3;
        else if(op=='c') s[i][0]=1,s[i][1]=2;
        else plc[++cur]=i;
    }
    For(i,1,m) a[i]= {read(),getc()-'A'+1,read(),getc()-'A'+1}; //?
    For(i,0,(1<<cur)-1) {
        tot=num=cnt=top=0;
        flag=0;
        For(j,0,n<<1) low[j]=dfn[j]=scc[j]=head[j]=0;
        For(j,1,cur) s[plc[j]][0]=1,s[plc[j]][1]=((1<<(j-1))&i)?2:3;
        For(j,1,m) {
            int h1=-1,h2=-1;
            if(s[a[j].a][0]==a[j].x) h1=0;
            else if(s[a[j].a][1]==a[j].x) h1=1;
            if(s[a[j].b][0]==a[j].y) h2=0;
            else if(s[a[j].b][1]==a[j].y) h2=1;
            if(h1==-1) continue;
            if(h2==-1) add(a[j].a+h1*n,a[j].a+(h1^1)*n);
            else add(a[j].a+h1*n,a[j].b+h2*n),add(a[j].b+(h2^1)*n,a[j].a+(h1^1)*n);
        }
        For(j,1,n<<1)if(!dfn[j]) tarjan(j);
        For(j,1,n) if(scc[j]==scc[n+j]) {
            flag=1;
            break;
        }
        if(flag) continue;
        For(j,1,n) putchar(s[j][scc[j]>scc[n+j]]+'A'-1);
        return 0;
    }
    puts("-1");
    return 0;
}

// 一个很妙的点：x 可以成为 a,b 的结合体，这样就能通过所有的车；将 3-SAT 问题通过一次暴力搜索变为 2-SAT 问题。

:::

例题 9

link：连续攻击游戏。

一个装备只能提供一个属性。

二分图匹配当中，一个点只能和一个点匹配。

我们把两个属性值当做两个点来连线。

此题可解。

:::success[代码]{close}

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+5;
vector<int> belong[N];
int a[N],b[N],cnt[N];
int num,ans,vis[N];

inline void dfs(int step){
    num++;
    ans=max(ans,step);
    if(num==2e7){
        cout<<ans;
        exit(0);
    }
    for(int i=0;i<belong[step+1].size();i++){
        int y=belong[step+1][i];
        if(vis[y]) continue;//去过了
        vis[y]=1;
        dfs(step+1);
        vis[y]=0;
    }
}

int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d %d",&a[i],&b[i]);
        cnt[a[i]]++,cnt[b[i]]++;
        belong[a[i]].push_back(i);
        belong[b[i]].push_back(i);
    }
    for(int i=1;i<=n;i++){
        if(cnt[a[i]]>=cnt[b[i]]) cnt[a[i]]--;
        else cnt[b[i]]--;
    }
    for(int i=1;;i++){
        if(cnt[i]==0) break;
        ans++;
    }
    dfs(0);
    cout<<ans;
    return 0;
}

:::