BZOJ 3757 苹果树

题目大意

给你一棵\(n\)个节点的树，每个点上有一个颜色\(col_i\)。现在有\(m\)个询问，每次给定4个数\((u,v,a,b)\)，询问\(u \rightarrow v\)路径上颜色的种类是多少，其中颜色\(a\)和颜色\(b\)算同一种颜色。

数据规模：\(1 \le n \le 50000, 1 \le m \le 10^5, 1 \le u, v, a, b, col_i \le n\)

题目分析

首先我们不考虑\(a,b\)的限制，然后这道题目就变成SPOJ COT2，套用树上莫队算法就可以搞定。现在考虑\(a,b\)限制，很显然，只有当颜色\(a\)和颜色\(b\)同时存在的时候才会是答案-1，于是我们再额外判一下是否\(a,b\)同时存在即可。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 10, BLK = 533;
vector<int> G[MAXN];
map<int, int> mp;
int father[MAXN][20], dfn[MAXN], pt[MAXN];
int col[MAXN], dep[MAXN], N, Q, sz;
int st[MAXN], ed[MAXN], tid;
int A[MAXN], B[MAXN];

namespace LCA {
    static const int POW = 19;
    void build() {
        for (int i = 1; (1 << i) <= N; ++ i) {
            for (int j = 1; j <= N; ++ j) {
                if (father[j][i - 1] == 0) continue;
                father[j][i] = father[father[j][i - 1]][i - 1];
            }
        }
    }
    int up(int u, int d) {
        for (int i = 0; d; ++ i, d >>= 1) {
            if (d & 1) u = father[u][i];
        }
        return u;
    }
    int ask(int u, int v) {
        if (dep[u] < dep[v]) swap(u, v);
        u = up(u, dep[u] - dep[v]);
        for (int i = POW; i >= 0; -- i) {
            if (father[u][i] == father[v][i]) continue;
            u = father[u][i]; v = father[v][i];
        }
        if (u != v) u = father[u][0];
        return u;
    }
}

struct Query {
    int l, r, i;
    Query() {}
    Query(int l, int r, int i) : l(l), r(r), i(i) {}
    const bool operator <(const Query &rhs) const {
        int bl1 = l / BLK, bl2 = rhs.l / BLK;
        if (bl1 == bl2) return r < rhs.r;
        else return bl1 < bl2;
    }
} q[MAXN];

bool isAnc(int u, int v) {
    return st[u] <= st[v] && ed[u] >= ed[v];
}

namespace COT2 {
    int ans[MAXN], cnt[MAXN], sz;
    bool vis[MAXN];
    int x, y, z;
    inline bool onWay(int v, int x, int y, int z) {
        return (isAnc(z, v) && (isAnc(v, x) || isAnc(v, y)));
    }
    inline void add(int x) {
        if ((++ cnt[x]) == 1) ++ sz;
    }
    inline void del(int x) {
        if ((-- cnt[x]) == 0) -- sz;
    }
    inline void gao(int v) {
        if (onWay(v, x, y, z)) {
            if (!vis[v]) {
                vis[v] = true; add(col[v]);
            }
        }
        else if (vis[v]) {
            vis[v] = false; del(col[v]);
        }
    }
    void go(int v, int to) {
        int z = LCA::ask(v, to);
        while (v != z) {
            gao(v);
            v = father[v][0];
        }
        gao(z); v = to;
        while (v != z) {
            gao(v);
            v = father[v][0];
        }
    }
    inline int check(int a, int b) {
        if (a == b) return 0;
        return cnt[a] && cnt[b];
    }
    void solve() {
        int v1 = 1, v2 = 1;
        x = y = z = 1; sz = 0;
        gao(v1);
        for (int i = 0; i < Q; ++ i) {
            x = q[i].l, y = q[i].r, z = LCA::ask(x, y);
            go(v1, q[i].l); v1 = q[i].l;
            go(v2, q[i].r); v2 = q[i].r;
            ans[q[i].i] = sz - check(A[q[i].i], B[q[i].i]);
        }
    }
}

void dfs(int u, int p) {
    dfn[u] = sz; pt[sz ++] = u;
    st[u] = ++ tid;
    father[u][0] = p; dep[u] = dep[p] + 1;
    for (int i = 0; i < (int)G[u].size(); ++ i) {
        int v = G[u][i]; if (v == p) continue;
        dfs(v, u);
    }
    ed[u] = ++ tid;
}

int main() {
    scanf("%d%d", &N, &Q);
    for (int i = 1; i <= N; ++ i) {
        scanf("%d", col + i);
    }
    for (int i = 1; i <= N; ++ i) {
        int x, y; scanf("%d%d", &x, &y);
        G[x].push_back(y); G[y].push_back(x);
    }
    tid = sz = 0;
    dfs(G[0][0], 0);
    LCA::build();
    for (int i = 0; i < Q; ++ i) {
        int u, v; scanf("%d%d%d%d", &u, &v, A + i, B + i);
        u = dfn[u]; v = dfn[v];
        if (u > v) swap(u, v);
        q[i] = Query(u, v, i);
    }
    sort(q, q + Q);
    for (int i = 0; i < Q; ++ i) {
        q[i].l = pt[q[i].l];
        q[i].r = pt[q[i].r];
    }
    COT2::solve();
    for (int i = 0; i < Q; ++ i) {
        printf("%d\n", COT2::ans[i]);
    }
    return 0;
}

• Relative Posts