SPOJ Count On Tree II

题目链接

题意

给出一棵大小为 $n$ 的树以及树上每个点的颜色,并且给出 $m$ 个询问 $(u,v)$ ,对每个询问求出 $u$ 到 $v$ 这条链上有多少不同的颜色
$n\leq 40000, m\leq 100000$

题解

第一次打树上莫队这东西
首先对于一条链的情况直接用普通莫队就可以解决
对于一棵树的情况,我们考虑如何将它转化为序列问题
可以使用欧拉序,我们将对每个点访问开始和结束时分别塞进序列里,就做出了欧拉序,例如样例
选区_155.png
对应的欧拉序就是
$\texttt{1 4 8 8 4 3 7 7 6 6 5 5 3 2 2 1}$
pre[u] 表示 u 点的访问开始时的标号, lst[u] 代表 u 点结束访问时的标号
假设我们观察 $(7,8)$ 这条链,发现 $\texttt{[pre[8]+1,pre[7]]}$ 这段区间刚好把链上每个点标记一遍,不在链上的点标记0遍或2遍
但是LCA并不在这段区间内,但是只有这一个点,就很好处理了
对于一段父子链发现也满足这个规律
那么我们就可以直接在欧拉序上跑莫队了
在算贡献时判断一下就行
具体的话看程序很好懂

程序

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

#define reg register
#define MAX_N 100007
#define MAX_M 200007
typedef long long ll;

int N, M;
int head[MAX_N], to[MAX_N << 1], nxt[MAX_N << 1], cap;
int fa[MAX_N][21], dep[MAX_N];
int pos[MAX_N], pre[MAX_N], lst[MAX_N], mp[MAX_N], dfn;
int col[MAX_N], colo[MAX_N], tot[MAX_N];
int res, ans[MAX_N];
bool vis[MAX_N];

struct query {
    int l, r, id;

    bool operator < (const query& rhs) const {
        if (pos[l] == pos[rhs.l]) {
            return (pos[l] & 1) ? r < rhs.r : r > rhs.r;
        }
        return pos[l] < pos[rhs.l];
    }
}q[MAX_M];

inline void addEdge (int u, int v) {
    nxt[++cap] = head[u];
    head[u] = cap;
    to[cap] = v;
}

inline void input () {
    read(N), read(M);
    for (int i = 1; i <= N; ++i)
        read(col[i]), colo[i] = col[i];
    int u, v;
    for (int i = 1; i < N; ++i) {
        read(u), read(v);
        addEdge(u, v);
        addEdge(v, u);
    }
    for (int i = 1; i <= M; ++i)
        read(q[i].l), read(q[i].r), q[i].id = i;
}

void dfs (int x) {
    pre[x] = ++dfn;
    mp[dfn] = x;
    for (int i = 1; i < 21; ++i)
        fa[x][i] = fa[fa[x][i - 1]][i - 1];
    for (int i = head[x]; i; i = nxt[i])
        if (to[i] != fa[x][0]) {
            dep[to[i]] = dep[x] + 1;
            fa[to[i]][0] = x;
            dfs(to[i]);
        }
    lst[x] = ++dfn;
    mp[dfn] = x;
}

inline void init () {
    dep[1] = 1;
    dfs(1);
    for (int i = 1; i <= M; ++i) {
        if (pre[q[i].l] > pre[q[i].r])
            std::swap(q[i].l, q[i].r);
        q[i] = (query){pre[q[i].l], pre[q[i].r], q[i].id};
    }
    int sqn = sqrt(dfn);
    for (int i = 1; i <= dfn; ++i)
        pos[i] = (i - 1) / sqn + 1;
    std::sort(q + 1, q + M + 1);
    std::sort(colo + 1, colo + N + 1);
    int top = std::unique(colo + 1, colo + N + 1) - colo - 1;
    for (int i = 1; i <= N; ++i)
        col[i] = std::lower_bound(colo + 1, colo + top + 1, col[i]) - colo;
}

inline int getLca (int u, int v) {
    if (dep[u] < dep[v]) std::swap(u, v);
    for (int i = 20; i >= 0; --i)
        if (dep[fa[u][i]] >= dep[v])
            u = fa[u][i];
    if (u == v) return u;
    for (int i = 20; i >= 0; --i)
        if (fa[u][i] != fa[v][i])
            u = fa[u][i], v = fa[v][i];
    return fa[u][0];
}

inline void modify (int x) {
    int y = mp[x];
    if (vis[y]) {
        if (!--tot[col[y]])
            res--;
    } else {
        if (!tot[col[y]]++)
            res++;
    }
    vis[y] ^= 1;
}

inline void solve () {
    int l = q[1].l + 1, r = q[1].l, lca;
    for (int i = 1; i <= M; ++i) {
        lca = getLca(mp[q[i].l], mp[q[i].r]);
        q[i].l++;
        while (l < q[i].l)
            modify(l++);
        while (q[i].l < l)
            modify(--l);
        while (q[i].r < r)
            modify(r--);
        while (r < q[i].r)
            modify(++r);
        ans[q[i].id] = res + (!tot[col[lca]]);
    }
    for (int i = 1; i <= M; ++i) printf("%d\n", ans[i]);
}

int main () {
    input();
    init();
    solve();
    return 0;
}

sys_con

OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注