题意与分析

题意是这样的，给定一颗节点有权值的树，然后给若干个询问，每次询问让你找出一条链上有多少个不同权值。

写这题之前要参看我的三个blog：Codeforces Round #326 Div. 2 E（树上利用倍增求LCA）、Codeforces Round #340 Div. 2 E（朴素莫队）和BZOJ-1086（树的分块），然后再看这几个Blog——

参考A：https://blog.sengxian.com/algorithms/mo-s-algorithm

参考B：https://www.cnblogs.com/oyking/p/4265823.html

参考C：https://blog.csdn.net/u014609452/article/details/50675370

参考D：https://www.cnblogs.com/RabbitHu/p/MoDuiTutorial.html

然后，至少抄的时候心里稍微明白了一点了23333

接下来，我们具体的分析一下树上莫队是如何实现的，以及具体的心路历程。

具体分析

莫队算法的进一步理解

莫队算法的核心只有5行：

while(pl < q[i].l) del(a[pl++]);

while(pl > q[i].l) add(a[--pl]);

while(pr < q[i].r) add(a[++pr]);

while(pr > q[i].r) del(a[pr--]);

ans[q[i].id] = sum;

那么它为啥在排序之后就work了呢？

左端点所在块编号确定时，右端点位置保证不下降，所以右端点移动最多造成的时间复杂度是$O(n)$的，总共左端点的块数是$\sqrt n$块，从而总时间复杂度为$O(n \sqrt n)$。
左端点所在块编号变动时，右端点移动最多有$O(n)$的时间复杂度（最坏从$n$移动回$1$），总共$\sqrt n$块，从而总时间复杂度也为$O(n\sqrt n)$。
块内左端点位置每次最多移动$\sqrt n$，一共$m$次询问，也就是一共移动$m$次，总时间复杂度为$O(m\sqrt n)$。

总上，莫队算法具有$O(n\sqrt n)$的时间复杂度，相当（在$n=10^5$范围）够用了。

树上的迁移

首先为了利用莫队算法，我们需要对树进行分块。利用BZOJ-1086的分块方法可以确保比较好的分块性质：每一块“相对地”聚在一起，且大小在$[BLOCK\_SIZE, 3BLOCK\_SIZE]$之间。然后接下来然后我们还是要对所有询问进行排序。排序依据是左端点所在块的编号、右端点所在块的编号、时间。

最后，从朴素莫队迁移过来的一个重要问题就是：如何移动起点终点？

在序列中，左右端点的移动方式是显然的，一个端点的移动只有两个方向——左和右；而它们带来的影响也是显然的——区间增加或删除一个元素。然而树上莫队却不是非常显然……最佳的（dalao想出来的）方案是：维护一个vis布尔数组，记录每个节点是否在当前处理的路径上（LCA非常难办，我们在维护路径上的点时不包括LCA，求答案的时候临时把LCA加上）。每次从上一个询问$(u_s,v_s)$转移到当前询问$(u_t,v_t)$时，我们要做的是把路径$(u_s,u_t)$和$(v_s,v_t)$上的点的vis逐个取反，同时对应地维护答案。

这样为啥是对的呢？VFleaKing（一位julao）的博客中（现在似乎没法打开了）有证明，证明部分摘录如下（$\oplus$表示类似异或的操作，即节点出现两次会消去）：

（摘者注：$T(v,u)$可以理解为一次$(u,v)$树上链的操作。）

\[T(v, u) = S(root, v) \oplus S(root, u)$$（之前的摘者注：显然等式右侧是u到v的路径上除lca以外的点）
观察将$cur_V$移动到$target_V$前后$T(cur_V, cur_U)$变化：
$$T(cur_V, cur_U) = S(root, cur_V) \oplus S(root, cur_U) \\
T(target_V, cur_U) = S(root, target_V) \oplus S(root, cur_U)\]

取对称差：（摘者注：目的是观察移动区间时出现了什么变化）

\[T(cur_V, cur_U) \oplus T(target_V, cur_U) = (S(root, cur_V) \oplus S(root, cur_U)) \oplus (S(root, target_V) \oplus S(root, cur_U))
\]

由于对称差的交换律、结合律：

\[T(cur_V, cur_U) \oplus T(target_V, cur_U)= S(root, cur_V) \oplus S(root, target_V)
\]

两边同时$\oplus T(cur_V, cur_U)$：（摘者注：清理左边）

\[T(target_V, cur_U)= T(cur_V, cur_U) \oplus S(root, cur_V) \oplus S(root, target_V)
\]

发现最后两项很爽……哇哈哈（摘者注：利用这种操作的性质）

\[T(target_V, cur_U)= T(cur_V, cur_U) \oplus T(cur_V, target_V)
\]

（摘者注：最后可以发现，左端点A->B只需要对现有区间做一个(A,B)的反向操作即可，而这正是莫队算法的要求）

这就是树上莫队了。是不是很简单（大雾）

这一题的应用

我们注意到，统计的是链上不同点的个数，这个恰恰是可以有这种性质的：$ans[l,r]$可以（在$O(1)$时间）得到$ans[l+1,r],ans[l-1,r],ans[l,r+1],ans[l,r-1]$。于是，这里就可以应用树上莫队算法了。

具体的实现类似莫队，只是对区间的处理有点小不同：考虑$(x,y)$间路径的信息，如果$x$是$y$的祖先，那么所求信息就为$x$和$y$最后出现的位置之间的信息（这里代码的实现很简单：如果二者深度不一样，就一格一格地跳上来，反正也不需要快速维护，莫队已经保证了；如果$x$是$y$的祖先——不失一般性，设$x<y$，那么到这里已经结束了）；如果$x$不是$y$的祖先，那么二者逐步逐步地边跳到LCA边维护信息即可，最后全部的操作结束后再把LCA加上即可（原因上面已经说了）。

预处理有两个：1）dfs分块、判断深度，2）做一个倍增LCA（Tarjan似乎也可以？）。

代码

/*

 * Filename: spoj_cot2.cpp

 * Date: 2018-11-13

 */

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

#define PB emplace_back

#define MP make_pair

#define fi first

#define se second

#define rep(i,a,b) for(repType i=(a); i<=(b); ++i)

#define per(i,a,b) for(repType i=(a); i>=(b); --i)

#define ZERO(x) memset(x, 0, sizeof(x))

#define MS(x,y) memset(x, y, sizeof(x))

#define ALL(x) (x).begin(), (x).end()

#define QUICKIO                  \

    ios::sync_with_stdio(false); \

    cin.tie(0);                  \

    cout.tie(0);

#define DEBUG(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)

using namespace std;

using pi=pair<int,int>;

using repType=int;

using ll=long long;

using ld=long double;

using ull=unsigned long long;

const int MAXN=40005, MAXM=100005;

const int MAXE=MAXN<<1, MLOG=20;

int val[MAXN];

vector<int> G[MAXN];

int n,m;

int stk[MAXN], top=0;

int blk[MAXN], bcnt, bsz;

struct Query

{

    int u, v, id;

    void read(int i)

    {

        id=i;

        scanf("%d%d", &u, &v);

    }

    void adjust()

    {

        if(blk[u]>blk[v]) swap(u,v);

    }

    bool operator < (const Query& rhs) const

    {

        if(blk[u]!=blk[rhs.u]) return blk[u]<blk[rhs.u];

        else return blk[v]<blk[rhs.v]; // Right Range First

    }

} asks[MAXM];

int ans[MAXM];

// Graph

inline void init()

{

    rep(i,1,n) G[i].clear();

}

// Discretization

void get_hash(int a[], int n)

{

    static int tmp[MAXM];

    int cnt=0;

    rep(i,1,n) tmp[cnt++]=a[i];

    sort(tmp,tmp+cnt);

    cnt=unique(tmp,tmp+cnt)-tmp;

    rep(i,1,n) a[i]=lower_bound(tmp,tmp+cnt,a[i])-tmp+1;

}

// Input Read

inline void read_input()

{

    scanf("%d%d", &n, &m);

    rep(i,1,n) scanf("%d", &val[i]);

    get_hash(val, n);

    init();

    rep(i,1,n-1)

    {

        int u,v;

        scanf("%d%d", &u, &v);

        G[u].PB(v);

        G[v].PB(u);

    }

    rep(i,0,m-1) asks[i].read(i);

}

// Find Blks: See BZOJ 1086

inline void add_blk(int& cnt)

{

    while(cnt--) blk[stk[--top]]=bcnt;

    bcnt++;

    cnt=0;

}

inline void rst_blk()

{

    while(top) blk[stk[--top]]=bcnt-1;

}

int dfs_blk(int now, int pre)

{

    int sz=0;

    rep(i,0,int(G[now].size())-1) if(G[now][i]!=pre)

    {

        sz+=dfs_blk(G[now][i], now);

        if(sz>=bsz) add_blk(sz);

    }

    stk[top++]=now;

    sz++;

    if(sz>=bsz) add_blk(sz);

    return sz;

}

inline void init_blk()

{

    bsz=max(1,(int)sqrt(n));

    dfs_blk(1,0);

    rst_blk();

}

// Ask for RMQs: LCA

int fa[MLOG][MAXM], dep[MAXM];

inline void dfs_lca(int u, int f, int ndep)

{

    dep[u]=ndep;

    fa[0][u]=f;

    rep(i,0,int(G[u].size()-1)) if(G[u][i]!=f)

        dfs_lca(G[u][i],u,ndep+1);

}

inline void init_lca()

{

    dfs_lca(1,-1,0);

    rep(k,0,MLOG-2)

    {

        rep(u,1,n)

        {

            if(fa[k][u]==-1) fa[k+1][u]=-1;

            else fa[k+1][u]=fa[k][fa[k][u]];

        }

    }

}

int ask_lca(int u,int v)

{

    if(dep[u]<dep[v]) swap(u,v);

    rep(k,0,MLOG-1)

        if((dep[u]-dep[v]) & (1<<k)) u=fa[k][u];

    if(u==v) return u;

    per(k,MLOG-1,0)

        if(fa[k][u]!=fa[k][v])

        {

            u=fa[k][u];

            v=fa[k][v];

        }

    return fa[0][u];

}

// Mo's algorithm

bool vis[MAXM];

int diff, cnt[MAXM];

inline void xor_node(int u)

{

    if(vis[u])

    {

        vis[u]=false;

        diff-=(--cnt[val[u]]==0);

    }

    else

    {

        vis[u]=true;

        diff+=(++cnt[val[u]]==1);

    }

}

inline void xor_path_without_lca(int u, int v)

{

    if(dep[u]<dep[v]) swap(u,v);

    while(dep[u]!=dep[v])

    {

        xor_node(u);

        u=fa[0][u];

    }

    while(u!=v)

    {

        xor_node(u);

        u=fa[0][u];

        xor_node(v);

        v=fa[0][v];

    }

}

inline void mv_node(int u, int v, int taru, int tarv)

{

    xor_path_without_lca(u, taru);

    xor_path_without_lca(v, tarv);

    xor_node(ask_lca(u,v));

    xor_node(ask_lca(taru,tarv));

}

inline void make_ans()

{

    rep(i,0,m-1)

        asks[i].adjust(); // make every query has a u,v that u<v

    sort(asks,asks+m);

    int nowu=1,nowv=1; xor_node(1);

    rep(i,0,m-1) // Mo's algorithm -- basis

    {

        mv_node(nowu, nowv, asks[i].u, asks[i].v);

        ans[asks[i].id]=diff;

        nowu=asks[i].u;

        nowv=asks[i].v;

    }

}

inline void print_ans()

{

    rep(i,0,m-1) printf("%d\n", ans[i]);

}

int main()

{

    read_input();

    init_blk();

    init_lca();

    make_ans();

    print_ans();

    return 0;

}

巴特西

「日常训练&知识学习」莫队算法（二）：树上莫队（Count on a tree II，SPOJ COT2）

题意与分析

具体分析

莫队算法的进一步理解

树上的迁移

这一题的应用

代码

最新文章

热门文章