树上莫队

在将莫队推广到树上之前，我们肯定都已经能够熟练掌握莫队算法了。而且，非常清楚它的时间复杂度的证明。

普通莫队算法教程

现在，我们要考虑这样一种问题：存在多个独立询问，每次询问一棵树上两点之间的路径的一些特征。这类问题一般可用树链剖分解决，如果不行，我们可以考虑树上莫队。

欧拉序

欧拉序是指在遍历一棵树时，每次新进入一个节点或从一个节点出来时，将这个节点的编号记录下来，形成的序列。

这样，一棵树的欧拉序满足以下性质：

• 两个相同元素之间的序列描述的是该节点为根的子树
• 两个相同元素之间不可能出现单独的元素

这样，一棵树就能够用欧拉序线性表示了。欧拉序就是将莫队推广到树上的工具，而且树上莫队的实质就是在欧拉序上跑序列莫队。

欧拉序与树链

如果我们想通过欧拉序上的莫队，解决树上的莫队问题，有一个待解决的问题就是，如何从欧拉序中提取出链的信息？

因为我们知道，欧拉序描述的是子树信息，因此我们需要将无关的子树从一段序列中抛掉。

首先，我们需要将链 $(x,y$) 的左右端点出现在序列中的位置所夹的子序列提取出来。由于每个端点会出现两次，所以究竟提取哪一段区间是有讲究的：
– 如果 x 和 y 存在子树包含关系，那么在序列中一定形如：$\cdots x\cdots y\cdots y\cdots x\cdots$。那么提取第一个 x 和第一个 y 之间的序列即可。
– 如果 x 和 y 不存在子树包含关系，那么序列一定形如：$\cdots x\cdots x\cdots y\cdots y \cdots$。那么提取第二个 x 和第一个 y 之间的序列即可。

如果我们见到序列中成对的数字，我们就把它们一起抛掉。因为如果不在链的 LCA 处，不可能发生进入一个点再出来的情况。而链的 LCA 处呢？这里又要分情况了。

1.LCA 在链的端点处，说明是上面的第 1 种情况。这时 LCA 就是 $x$，由于 x 在序列中肯定只出现了一次，所以这时 LCA 包含在序列中。

2.LCA 不在链的端点处，说明是上面的第 2 种情况。这时，LCA 肯定没有在提取的序列中出现，因此我们必须将 LCA 补充到答案中去。

实现

首先，我们需要求出欧拉序。

其次，我们将询问排序，运行普通莫队。

为了实现 “抛掉重复元素” 的操作，我们记录每个元素在当前区间 $[L,R]$中出现的次数。

在最终统计答案时，我们还需要将结果加上 LCA 的影响。

所以大致流程大概是：

int L, R, ANS;
void ladd() {/*do something*/}
void radd() {/*do something*/}
void lmns() {/*do something*/}
void rmns() {/*do something*/}
void work()
{
    for(int i=1; i<=M; i++)
    {
        while(L > Q[i].l) lmns();
        while(R < Q[i].r) radd();
        while(L < Q[i].l) ladd();
        while(R > Q[i].r) rmns();
        int lca = getlca(Q[i].a, Q[i].b);
        ANS = /*do something with lca*/;
    }
}

如果还需要支持修改，类似于普通带修改莫队。

题目

Count on a tree II(SPOJ10707) 树上莫队

这道题要你求树上的链中出现的不同元素个数，将 HH 的项链放到树上即可。

如果你想吐槽我代码写得又臭又长。。。

好吧我也觉得是这么回事。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#define BS 270
#define MX 100005

using namespace std;

struct QUERY
{
    int l, r, lb, id;

    bool operator < (const QUERY& t) const {return (lb!=t.lb) ? (lb<t.lb) : (r<t.r);}
} QUR[MX];

struct GRAPH
{
    int fst[MX], nxt[MX], v[MX], n, lnum;

    void addeg(int nu, int nv)
    {
        nxt[++lnum] = fst[nu];
        fst[nu] = lnum;
        v[lnum] = nv;
    }

    int fa[17][MX], dep[MX];

    void dfs(int x, int f, int d)
    {
        fa[0][x] = f;
        dep[x] = d;
        for(int i=fst[x]; i; i=nxt[i])
            if(v[i] != f)
                dfs(v[i], x, d+1);
    }

    void prework()
    {
        dfs(1, 0, 1);
        for(int j=1; j<17; j++)
            for(int i=1; i<=n; i++)
                fa[j][i] = fa[j-1][fa[j-1][i]];
    }

    int lca(int x, int y)
    {
        if(dep[y] > dep[x]) swap(x,y);
        for(int i=16; i>=0; i--)
            if(dep[fa[i][x]] >= dep[y])
                x = fa[i][x];
        if(x == y) return x;
        for(int i=16; i>=0; i--)
            if(fa[i][x] != fa[i][y])
                x = fa[i][x], y = fa[i][y];
        return fa[0][x];
    }
} G;

int N, M, VAL[MX], COL[MX];
int SEQ[MX], DEP[MX], RAG[MX][2], VCNT;

void input()
{
    int a, b;
    scanf("%d%d", &N, &M);
    for(int i=1; i<=N; i++) scanf("%d", &VAL[i]);
    for(int i=1; i<N; i++)
    {
        scanf("%d%d", &a, &b);
        G.addeg(a, b);
        G.addeg(b, a);
    }
    for(int i=1; i<=M; i++) scanf("%d%d", &QUR[i].l, &QUR[i].r);
}

void squeeze()
{
    static int real[MX], rnum;
    rnum = 0;
    for(int i=1; i<=N; i++) real[++rnum] = VAL[i];
    sort(real+1, real+rnum+1);
    rnum = unique(real+1, real+rnum+1) - real - 1;
    for(int i=1; i<=N; i++) VAL[i] = lower_bound(real+1, real+rnum+1, VAL[i]) - real;
}

void dfs(int x, int f, int d)
{
    DEP[x] = d;
    SEQ[++VCNT] = x;
    RAG[x][0] = VCNT;
    for(int i=G.fst[x]; i; i=G.nxt[i])
        if(G.v[i] != f)
            dfs(G.v[i], x, d+1);
    SEQ[++VCNT] = x;
    RAG[x][1] = VCNT;
}

bool contain(int a, int b)
{
    int la = RAG[a][0], ra = RAG[a][1];
    int lb = RAG[b][0], rb = RAG[b][1];
    if(la<=lb && rb<=ra) return true;
    if(lb<=ra && ra<=rb) return true;
    return false;
}

void prework()
{
    G.n = N;
    dfs(1, 0, 1);
    G.prework();
    for(int i=1; i<=M; i++)
    {
        int l, r;
        if(contain(QUR[i].l, QUR[i].r))
        {
            l = RAG[QUR[i].l][0];
            r = RAG[QUR[i].r][0];
        }
        else
        {
            l = min(RAG[QUR[i].l][1], RAG[QUR[i].r][1]);
            r = max(RAG[QUR[i].l][0], RAG[QUR[i].r][0]);
        }
        if(l > r) swap(l, r);
        QUR[i].l = l;
        QUR[i].r = r;
        QUR[i].lb = l / BS;
        QUR[i].id = i;
    }
    for(int i=1; i<=N*2; i++) COL[i] = VAL[SEQ[i]];
    sort(QUR+1, QUR+M+1);
}

int APP[MX], CNT[MX], L, R, ANS;

void del(int x)
{
    if(CNT[x] == 1) ANS--;
    CNT[x] --;
}

void add(int x)
{
    if(CNT[x] == 0) ANS++;
    CNT[x] ++;
}

void ladd()
{
    if(APP[SEQ[L]]) del(COL[L]);
    else add(COL[L]);
    APP[SEQ[L]] ^= 1;
    L ++;
}

void lmns()
{
    L --;
    APP[SEQ[L]] ^= 1;
    if(APP[SEQ[L]]) add(COL[L]);
    else del(COL[L]);
}

void radd()
{
    R ++;
    APP[SEQ[R]] ^= 1;
    if(APP[SEQ[R]]) add(COL[R]);
    else del(COL[R]);
}

void rmns()
{
    if(APP[SEQ[R]]) del(COL[R]);
    else add(COL[R]);
    APP[SEQ[R]] ^= 1;
    R --;
}

void work()
{
    static int ans[MX];
    L = 1, R = 0;
    for(int i=1; i<=M; i++)
    {
        while(L > QUR[i].l) lmns();
        while(R < QUR[i].r) radd();
        while(L < QUR[i].l) ladd();
        while(R > QUR[i].r) rmns();
        ans[QUR[i].id] = ANS+(CNT[VAL[G.lca(SEQ[QUR[i].l], SEQ[QUR[i].r])]] == 0);
    }
    for(int i=1; i<=M; i++) printf("%d\n", ans[i]);
}

int main()
{
    input();
    squeeze();
    prework();
    work();
    return 0;
}

Haruna’s Breakfast

求树链上的数的 mex，带修改

求 mex 需要用 $O(1)$插入，$O(n^{2/3})$以内查询的方式。实际上可以用分块。每一个块维护当前块内是否存在空缺，块大小 $\Theta(n^{1/2})$，插入 $O(1)$，询问 $O(n^{1/2})$。

如果你还是想吐槽我代码写得又臭又长。。。

实际上我也是这么觉得的。。。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <set>
#define MX 50005
#define BS 2000
#define BS2 200

using namespace std;

struct QUERY
{
    int l, r, t, lb, rb, id;

    bool operator < (const QUERY& q) const
    {
        return (lb!=q.lb) ? (lb<q.lb) : ((rb!=q.rb) ? (rb<q.rb) : (t<q.t));
    }
} QUR[MX];

struct CHANGE
{
    int p, x, y;
} CNG[MX];

struct GRAPH
{
    int fst[MX], nxt[MX*2], v[MX*2], lnum;

    void addeg(int nu, int nv)
    {
        nxt[++lnum] = fst[nu];
        fst[nu] = lnum;
        v[lnum] = nv;
    }

    int seq[MX*2], dep[MX], rag[MX*2][2], rmq[17][MX*2], logs[MX*2], vcnt;

    void dfs(int x, int f, int d)
    {
        dep[x] = d;
        seq[++vcnt] = x;
        rag[x][0] = vcnt;
        rmq[0][vcnt] = x;
        for(int i=fst[x]; i; i=nxt[i])
            if(v[i] != f)
            {
                dfs(v[i], x, d+1);
                seq[++vcnt] = x;
                rmq[0][vcnt] = x;
            }
        rag[x][1] = vcnt;
    }

    void prework(int n)
    {
        logs[0] = -1;
        dfs(1, 0, 1);
        for(int i=1; i<=vcnt; i++) logs[i] = logs[i>>1] + 1;
        for(int i=1; i<17; i++)
            for(int j=1; j+(1<<i)-1<=vcnt; j++)
            {
                int l = rmq[i-1][j], r = rmq[i-1][j+(1<<(i-1))];
                if(dep[l] <= dep[r]) rmq[i][j] = l;
                else rmq[i][j] = r;
            }
    }

    int lca(int x, int y)
    {
        int l = min(rag[x][0], rag[y][0]);
        int r = max(rag[x][1], rag[y][1]);
        int w = logs[r-l+1];
        int ls = rmq[w][l];
        int rs = rmq[w][r-(1<<w)+1];
        if(dep[ls] <= dep[rs]) return ls;
        else return rs;
    }
} G;

struct MEX
{
    int n, b;
    int bcnt[MX];
    int cnt[MX];
    int bel[MX];

    void init(int v)
    {
        n = v;
        b = n/BS2;
        for(int i=0; i<=n; i++) bel[i] = i/BS2;
    }

    void add(int x)
    {
        if(x>n) return;
        cnt[x] ++;
        if(cnt[x] == 1) bcnt[bel[x]] ++;
    }

    void mns(int x)
    {
        if(x>n) return;
        cnt[x] --;
        if(cnt[x] == 0) bcnt[bel[x]] --;
    }

    int mex()
    {
        for(int i=0; i<=b; i++)
            if(bcnt[i] != BS2)
                for(int j=i*BS2; j<=n+1; j++)
                    if(cnt[j] <= 0)
                        return j;
    }
} B;

int N, M, Q, C;
int VAL[MX];
int RAG[MX][2], SEQ[MX*2], CNT;

bool contain(int x, int y)      // x contain y
{
    int lx = RAG[x][0], rx = RAG[x][1];
    int ly = RAG[y][0], ry = RAG[y][1];
    if(lx<=ly && ry<=rx) return true;
    else return false;
}

void dfs(int x, int f)
{
    SEQ[++CNT] = x;
    RAG[x][0] = CNT;
    for(int i=G.fst[x]; i; i=G.nxt[i])
        if(G.v[i] != f)
            dfs(G.v[i], x);
    SEQ[++CNT] = x;
    RAG[x][1] = CNT;
}

int read()
{
    int x = 0; char ch = getchar();
    while(!isdigit(ch)) ch = getchar();
    while(isdigit(ch)) x = x*10+ch-'0', ch = getchar();
    return x;
}

void input()
{
    static int seq[MX];
    int a, b, c;
    N = read(), M = read();
    for(int i=1; i<=N; i++) seq[i] = VAL[i] = read();;
    for(int i=1; i<N; i++)
    {
        a = read(), b = read();
        G.addeg(a, b);
        G.addeg(b, a);
    }
    for(int i=1; i<=M; i++)
    {
        a = read(), b = read(), c = read();
        if(a)
        {
            Q++;
            QUR[Q] = (QUERY){b, c, C, 0, 0, Q};
        }
        else
        {
            C++;
            CNG[C] = (CHANGE){b, seq[b], c};
            seq[b] = c;
        }
    }
}

void prework()
{
    G.prework(N);
    B.init(N);
    dfs(1, 0);
    for(int i=1; i<=Q; i++)
    {
        int l, r;
        if(contain(QUR[i].l, QUR[i].r) || contain(QUR[i].r, QUR[i].l))
        {
            l = RAG[QUR[i].l][0];
            r = RAG[QUR[i].r][0];
        }
        else
        {
            l = min(RAG[QUR[i].l][1], RAG[QUR[i].r][1]);
            r = max(RAG[QUR[i].l][0], RAG[QUR[i].r][0]);
        }
        if(l > r) swap(l, r);
        QUR[i].l = l;
        QUR[i].r = r;
        QUR[i].lb = l/BS;
        QUR[i].rb = r/BS;
    }
    sort(QUR+1, QUR+Q+1);
}

int L, R, T;
int APP[MX];

void tadd()
{
    T++;
    if(APP[CNG[T].p]) B.mns(CNG[T].x), B.add(CNG[T].y);
    VAL[CNG[T].p] = CNG[T].y;
}

void tmns()
{
    if(APP[CNG[T].p]) B.mns(CNG[T].y), B.add(CNG[T].x);
    VAL[CNG[T].p] = CNG[T].x;
    T--;
}

void ladd()
{
    APP[SEQ[L]] ^= 1;
    if(APP[SEQ[L]]) B.add(VAL[SEQ[L]]);
    else B.mns(VAL[SEQ[L]]);
    L++;
}

void lmns()
{
    L--;
    APP[SEQ[L]] ^= 1;
    if(APP[SEQ[L]]) B.add(VAL[SEQ[L]]);
    else B.mns(VAL[SEQ[L]]);
}

void radd()
{
    R++;
    APP[SEQ[R]] ^= 1;
    if(APP[SEQ[R]]) B.add(VAL[SEQ[R]]);
    else B.mns(VAL[SEQ[R]]);
}

void rmns()
{
    APP[SEQ[R]] ^= 1;
    if(APP[SEQ[R]]) B.add(VAL[SEQ[R]]);
    else B.mns(VAL[SEQ[R]]);
    R--;
}

void work()
{
    L = 1, R = 0, T = 0;
    static int ans[MX];
    for(int i=1; i<=Q; i++)
    {
        while(L > QUR[i].l) lmns();
        while(R < QUR[i].r) radd();
        while(L < QUR[i].l) ladd();
        while(R > QUR[i].r) rmns();
        while(T < QUR[i].t) tadd();
        while(T > QUR[i].t) tmns();
        int anc = G.lca(SEQ[QUR[i].l], SEQ[QUR[i].r]);
        B.add(VAL[anc]);
        ans[QUR[i].id] = B.mex();
        B.mns(VAL[anc]);
    }
    for(int i=1; i<=Q; i++) printf("%d\n", ans[i]);
}

int main()
{
    input();
    prework();
    work();
    return 0;
}

(但是我觉得我的每一行代码都是有用的啊，除了压行外，根本不可能精简，不信你删掉几行再提交试试)