Codeforces Round #497 Div1 D.Ants

给定一棵$n$ 个节点的树,以及 $m$ 对树链,要求从每对树链中选取一个树链,满足任意两对树链没有交集。构造任意一组合法方案输出,或判定无解。

$n\leq 10^5,m\leq 10^4$

打比赛的时候看到这个题,自以为一眼秒了,就不顾一切去码码码了。那时候的做法就是直接树剖来优化点点之间连边。但是写完后才发现这样会造成一个 SAT 内部点互相联通的情况,后来怎么想都不会处理,到比赛最后也没想到靠谱的做法。

这个是我陷入的一个思维误区,如果用扩展连通性的思想拿线段树优化建图来优化 2-SAT 的话,不可避免会造成一个 SAT 内部之间点相连的情况。正确的做法应该是拿增加变量的思想来优化 2-SAT,即线段树上每个节点是有其具体意义的。

对于这道题来说,我们考虑对于每条边以所有覆盖了这条边的链对造一棵线段树,对于线段树上每个节点 $\mathrm{T_0, T_1}$ 分别代表这条边所属的链对是否是在这个节点所代表的区间中。不妨令 $\mathrm{X, Y}$ 为 $\mathrm{T}$ 的 两个儿子节点,那么我们只需要连边

$$\mathrm{(T_0 \rightarrow X_0,Y_0)(X_1, Y_1 \rightarrow T_1)(X_1 \rightarrow Y_0)(Y_1 \rightarrow X_0)}$$

具体含义显然,不再赘述。

但是直接这样做复杂度显然是不对的,容易发现,对于任意两条边所对应的线段树来说,本质不同的只会有 $O(M)$ 个。所以我们差分后处理即可,儿子向父亲的转移可以直接线段树合并,具体细节参考代码。

复杂度 $\mathcal{O(m(\log m + \log n))}$

#include <bits/stdc++.h>

using namespace std;

#define ll             long long
#define db            double
#define up(i,j,n)        for (int i = j; i <= n; i++)
#define down(i,j,n)    for (int i = j; i >= n; i--)
#define cadd(a,b)        a = add (a, b)
#define cpop(a,b)        a = pop (a, b)
#define cmul(a,b)        a = mul (a, b)
#define pr            pair<int, int>
#define fi            first
#define se            second
#define SZ(x)        (int)x.size()
#define bin(i)        (1 << (i))
#define Auto(i,node)    for (int i = LINK[node]; i; i = e[i].next)

template<typename T> inline bool cmax(T & x, T y){return y > x ? x = y, true : false;}
template<typename T> inline bool cmin(T & x, T y){return y < x ? x = y, true : false;}
template<typename T> inline T dmax(T x, T y){return x > y ? x : y;}
template<typename T> inline T dmin(T x, T y){return x < y ? x : y;}

const int MAXN = 1e5 + 5;
const int oo = 0x3f3f3f3f;
const int MAXM = 2e5 * 20 + 5;

int N, M, ss[MAXN][2], cnt, tree_cnt, n, bt[MAXM], scc;

inline int r(int x) { return x <= M ? x : x - M; }

struct tree {
    int o[2], son[2], siz;
}t[MAXM];

namespace SAT {

    struct edge {
        int y, next;
    }e[MAXM << 3];

    int LINK[MAXM], len = 0;

    inline void ins(int x, int y){
        e[++len].next = LINK[x]; LINK[x] = len;
        e[len].y = y;
//        printf("%d %d\n", x, y);
    }    

    inline int NewNode(int s0, int s1, int siz){
        int k = ++tree_cnt;
        t[k].son[0] = s0; t[k].son[1] = s1;
        t[k].siz = siz;
        return k;
    }

    void Merge(int &k, int x){
        if (!k || !x) return (void)(k += x);
        k = NewNode(t[k].son[0], t[k].son[1], t[k].siz + t[x].siz);
        t[k].o[0] = ++cnt;
        t[k].o[1] = ++cnt;
        Merge(t[k].son[0], t[x].son[0]);
        Merge(t[k].son[1], t[x].son[1]);
        int s0 = t[k].son[0], s1 = t[k].son[1];
        if (s0) ins(t[s0].o[1], t[k].o[1]), ins(t[k].o[0], t[s0].o[0]);
        if (s1) ins(t[s1].o[1], t[k].o[1]), ins(t[k].o[0], t[s1].o[0]);
        if (s0 && s1)
            ins(t[s0].o[1], t[s1].o[0]),
            ins(t[s1].o[1], t[s0].o[0]);        
    }

    void ins(int le, int ri, int &k, pr w){
        k = NewNode(t[k].son[0], t[k].son[1], t[k].siz + 1);
        if (le == ri) {
            t[k].o[0] = ss[r(w.fi)][w.se ^ 1];
            t[k].o[1] = ss[r(w.fi)][w.se];
            return;
        } 
        t[k].o[0] = ++cnt;
        t[k].o[1] = ++cnt;
        int mi = (le + ri) >> 1;
        w.fi <= mi ? ins(le, mi, t[k].son[0], w) :
            ins(mi + 1, ri, t[k].son[1], w);
        int s0 = t[k].son[0], s1 = t[k].son[1];
        if (s0) ins(t[s0].o[1], t[k].o[1]), ins(t[k].o[0], t[s0].o[0]);
        if (s1) ins(t[s1].o[1], t[k].o[1]), ins(t[k].o[0], t[s1].o[0]);
        if (s0 && s1)
            ins(t[s0].o[1], t[s1].o[0]),
            ins(t[s1].o[1], t[s0].o[0]);                
    }

    void del(int le, int ri, int &k, int o){
        k = NewNode(t[k].son[0], t[k].son[1], t[k].siz - 1);
        t[k].o[0] = ++cnt; t[k].o[1] = ++cnt;
        if (le == ri) return;
        int mi = (le + ri) >> 1;
        o <= mi ? del(le, mi, t[k].son[0], o) :
        del(mi + 1, ri, t[k].son[1], o);
        if (t[k].son[0] && t[t[k].son[0]].siz == 0) t[k].son[0] = 0;
        if (t[k].son[1] && t[t[k].son[1]].siz == 0) t[k].son[1] = 0;
        int s0 = t[k].son[0], s1 = t[k].son[1];
        if (s0) ins(t[s0].o[1], t[k].o[1]), ins(t[k].o[0], t[s0].o[0]);
        if (s1) ins(t[s1].o[1], t[k].o[1]), ins(t[k].o[0], t[s1].o[0]);
        if (s0 && s1)
            ins(t[s0].o[1], t[s1].o[0]),
            ins(t[s1].o[1], t[s0].o[0]);        
    }

    void init(){
        scanf("%d", &M);
        n = M + M;
        up (i, 1, M) up (j, 0, 1) 
            ss[i][j] = ++cnt;
    }

    int dfn[MAXM], low[MAXM], sta[MAXM], top, ord;
    bool vis[MAXM];
    deque<int> q;

    void DFS(int node){
        dfn[node] = low[node] = ++ord;
        vis[node] = 1; sta[++top] = node;
        Auto (i, node) if (!dfn[e[i].y]) {
            DFS(e[i].y);
            cmin(low[node], low[e[i].y]);
        }else if (vis[e[i].y]) cmin(low[node], dfn[e[i].y]);
        if (low[node] == dfn[node]) {
            int tmp; scc++;
            do {
                tmp = sta[top--];
                vis[tmp] = 0;
                bt[tmp] = scc;
            }while (tmp != node);
        }
    }

    vector<int> G[MAXM];

    int deg[MAXM], col[MAXM], opp[MAXM];


    void main(){
        up (i, 1, cnt) if (!dfn[i])
            DFS(i);
        up (i, 1, M) if (bt[ss[i][0]] == bt[ss[i][1]])
            return (void)puts("NO");
        up (i, 1, tree_cnt) if (bt[t[i].o[0]] == bt[t[i].o[1]])
            return (void)puts("NO");
        up (i, 1, M) {
            opp[bt[ss[i][0]]] = bt[ss[i][1]];
            opp[bt[ss[i][1]]] = bt[ss[i][0]];
        }
        up (i, 1, tree_cnt) {
            opp[bt[t[i].o[0]]] = bt[t[i].o[1]];
            opp[bt[t[i].o[1]]] = bt[t[i].o[0]];
        }
        puts("YES");
        up (node, 1, cnt) Auto (i, node) {
            int x = node, y = e[i].y;
            if (bt[x] == bt[y]) continue;
            G[bt[y]].push_back(bt[x]);
            deg[bt[x]]++;
        }
        up (i, 1, scc) if (deg[i] == 0) 
            q.push_back(i);
        while (!q.empty()) {
            int node = q.front(); q.pop_front();
            if (col[node] != 0) continue;
            col[node] = 1; col[opp[node]] = -1;
            up (i, 0, SZ(G[node]) - 1) if (!--deg[G[node][i]])
                q.push_back(G[node][i]);
        }
        up (i, 1, M) {
            up (j, 0, 1) if (col[bt[ss[i][j]]] == 1)
                printf("%d", j + 1);
            puts("");
        }
    }

}
vector<pr> cg[MAXN][2];

namespace Tree {

    struct edge {
        int y, next;
    }e[MAXN << 1];

    int LINK[MAXN], len = 0, fa[MAXN][21], dep[MAXN];

    inline void ins(int x, int y){
        e[++len].next = LINK[x]; LINK[x] = len;
        e[len].y = y;
    }

    inline void Ins(int x, int y){
        ins(x, y);
        ins(y, x);
    }

    int LCA(int x, int y){
        if (dep[x] < dep[y]) swap(x, y);
        down (i, 20, 0) if (fa[x][i] && dep[fa[x][i]] >= dep[y])
            x = fa[x][i];
        if (x == y) return x;
        down (i, 20, 0) if (fa[x][i] && fa[x][i] != fa[y][i]) {
            x = fa[x][i];
            y = fa[y][i];
        }
        return fa[x][0];
    }

    int getanc(int x, int o){
        assert(dep[x] > dep[o]);
        down (i, 20, 0) if (dep[fa[x][i]] > dep[o])
            x = fa[x][i];
        return x;
    }

    void DFS(int node){
        up (i, 1, 20) fa[node][i] = fa[fa[node][i - 1]][i - 1];
        Auto (i, node) if (e[i].y != fa[node][0]) {
            fa[e[i].y][0] = node;
            dep[e[i].y] = dep[node] + 1;
            DFS(e[i].y);
        }
    }

    int reDFS(int node){
        int root = 0;
        Auto (i, node) if (e[i].y != fa[node][0]) 
            SAT::Merge(root, reDFS(e[i].y));
        up (i, 0, SZ(cg[node][0]) - 1)
            SAT::ins(1, n, root, cg[node][0][i]);
        up (i, 0, SZ(cg[node][1]) - 1)
            SAT::del(1, n, root, cg[node][1][i].fi);
        return root;
    }

    void main(){
        scanf("%d", &N);
        up (i, 2, N) {
            int x, y; scanf("%d%d", &x, &y);
            Ins(x, y);
        }
        DFS(dep[1] = 1);
        SAT::init();
        up (i, 1, M) {
            int xa, ya, xb, yb;
            scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
            int lca = LCA(xa, ya);
            if (xa != lca) cg[xa][0].push_back(make_pair(i, 0));
            if (ya != lca) cg[ya][0].push_back(make_pair(i, 0));
            if (lca != xa) cg[getanc(xa, lca)][1].push_back(make_pair(i, 0));
            if (lca != ya) cg[getanc(ya, lca)][1].push_back(make_pair(i, 0));
            lca = LCA(xb, yb);
            if (xb != lca) cg[xb][0].push_back(make_pair(i + M, 1));
            if (yb != lca) cg[yb][0].push_back(make_pair(i + M, 1));
            if (lca != xb) cg[getanc(xb, lca)][1].push_back(make_pair(i + M, 1));
            if (lca != yb) cg[getanc(yb, lca)][1].push_back(make_pair(i + M, 1));
        }
        reDFS(1);
    }

}

int main(){
#ifdef cydiater
    freopen("input.in", "r", stdin);
#endif
    Tree::main();
    SAT::main();
    return 0;
}