题解 P3603 【雪辉】

DPair · 2020-12-11 20:20:38 · 题解

提供一种纯树剖+bitset的写法。

喜提洛谷最慢解。

怎么人均树分块啊，感觉我要被lxl卡了

【思路】

首先又是数颜色又是mex的，很容易想到bitset。

一种很naive的想法就是树剖，然后去暴力合并bitset。

（然而这种naive的做法稍微改一改居然能过。）

也就是对于树剖后建出来的那一棵线段树，每一个节点存一个 bitset 表示这个区间内的并集。

然后你会发现空间开不下。

考虑怎么节约空间。

我们不难发现线段树越深的节点存的信息越少，到最后一层干脆只有 1 个数了。

于是考虑把线段树的最后两层割掉不用 bitset 维护，而用 pair 去维护。

这样空间缩小了四倍就可以卡过去了，最底下两层由于不用bitset，消耗空间相比之下基本可以忽略不计。

实现上由于要求 mex ，我用了手写 bitset 。

具体实现上其实也没什么特别的，线段树上合并信息就直接对两个 bitset 取或，然后就得到了一个 bitset 表示这些链的数集之并。

那么两个询问的结果都出来了，用 bitset 基本操作的 count 什么的乱搞一下就行了。

是在线的。

然后就一遍 A 了。

复杂度似乎是 O({nV\log^2n \over w}) 的？

所以我为什么能A啊。。。

【代码】

#include <cstdio>
#include <cstring>
#include <bits/stl_pair.h>
using std :: pair;
using std :: make_pair;
template <typename T>
inline void read(T &x){
    x = 0;int fu = 1;
    char c = getchar();
    while(c > 57 || c < 48){
        if(c == 45) fu = -1;
        c = getchar();
    }
    while(c <= 57 && c >= 48){
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    x *= fu;
}
template <typename T>
inline void fprint(T x){
    if(x < 0) putchar(45), x = -x;
    if(x > 9) fprint(x / 10);
    putchar(x % 10 + 48);
}
template <typename T>
inline void fprint(T x, char ch){
    fprint(x);putchar(ch);
}

#define MAXN 100005
typedef unsigned long long ULL;
int n, m, f;
const int V = 470;
const ULL MOD = 18446744073709551615ull;
struct Bitset{
    ULL bit[475];
    Bitset (){memset(bit, 0, sizeof(bit));}
    inline void ins(int x){
        bit[x >> 6] |= 1ull << (x & 63);
    }
    inline void del(int x){
        bit[x >> 6] &= (MOD ^ 1ull << (x & 63));
    }
    inline void clear(){memset(bit, 0, sizeof(bit));}
    inline Bitset operator | (const Bitset &b) const{
        Bitset ret;
        for (register int i = 0;i < V;i ++) ret.bit[i] = bit[i] | b.bit[i];
        return ret;
    }
    inline int mex(){
        for (register int i = 0;i < V;i ++){
            if(bit[i] ^ MOD){
                for (register int j = 0;j < 64;j ++){
                    if(!((bit[i] >> j) & 1)) return i << 6 | j;
                }
            }
        }
    }
    inline int count(){
        int ret = 0;
        for (register int i = 0;i < V;i ++){ret += __builtin_popcountll(bit[i]);}
        return ret;
    }
}t[MAXN];
int a[MAXN];

#define LSON rt << 1, l, mid
#define RSON rt << 1 | 1, mid + 1, r
typedef pair <int, int> pi;
pi val[MAXN << 2];
int b[MAXN], dep[MAXN], sz[MAXN], fa[MAXN], son[MAXN], id[MAXN], tp[MAXN];
int head[MAXN], e[MAXN << 1], nxt[MAXN << 1], cnt;
inline void add(int u, int v){
    nxt[++ cnt] = head[u];
    head[u] = cnt;
    e[cnt] = v;
}
void dfs1(int x, int pre){
    fa[x] = pre;dep[x] = dep[pre] + 1;sz[x] = 1;
    for (register int i = head[x];i;i = nxt[i]){
        if(e[i] == pre) continue;
        dfs1(e[i], x);
        sz[x] += sz[e[i]];
        if(sz[e[i]] > sz[son[x]]) son[x] = e[i];
    }
}
int tot;
void dfs2(int x, int tt){
    tp[x] = tt;id[x] = ++ tot;b[tot] = a[x];
    if(son[x]) dfs2(son[x], tt);
    for (register int i = head[x];i;i = nxt[i]){
        if(e[i] == son[x] || e[i] == fa[x]) continue;
        dfs2(e[i], e[i]);
    }
}
inline void pushup(int rt, int l, int r){
    if(r - l + 1 <= 2){
        val[rt].first = val[rt << 1].first;
        val[rt].second = val[rt << 1 | 1].first;
    }
    else {
        int mid = (l + r) >> 1;
        if(mid - l + 1 <= 2) {
            t[rt].clear();
            if(~val[rt << 1].first) t[rt].ins(val[rt << 1].first);
            if(~val[rt << 1].second) t[rt].ins(val[rt << 1].second);
        }
        else t[rt] = t[rt << 1];
        if(r - mid <= 2){
            if(~val[rt << 1 | 1].first) t[rt].ins(val[rt << 1 | 1].first);
            if(~val[rt << 1 | 1].second) t[rt].ins(val[rt << 1 | 1].second);
        }
        else t[rt] = t[rt] | t[rt << 1 | 1];
    }
}

#define LSON rt << 1, l, mid
#define RSON rt << 1 | 1, mid + 1, r

void build(int rt, int l, int r){
    if(l == r){
        val[rt].first = b[l];
        val[rt].second = -1;
        return ;
    }
    int mid = (l + r) >> 1;
    build(LSON);build(RSON);
    pushup(rt, l, r);
}

pi Query(int rt, int l, int r, int x, int y){
    if(x <= l && r <= y) return val[rt];
    int mid = (l + r) >> 1;
    if(x <= mid && y > mid) return make_pair(Query(LSON, x, y).first, Query(RSON, x, y).first);
    if(x <= mid) return Query(LSON, x, y);
    else return Query(RSON, x, y);
}

Bitset query(int rt, int l, int r, int x, int y){
    if(x <= l && r <= y){
        if(r - l + 1 <= 2) {
            Bitset ret;
            if(~val[rt].first) ret.ins(val[rt].first);
            if(~val[rt].second) ret.ins(val[rt].second);
            return ret;
        }
        else return t[rt];
    }
    Bitset ret;
    int mid = (l + r) >> 1;
    if(x <= mid) ret = query(LSON, x, y);
    if(y > mid) ret = ret | query(RSON, x, y);
    return ret;
}
Bitset QUERY(int u, int v){
    Bitset ret;
    while(tp[u] ^ tp[v]){
        if(dep[tp[u]] < dep[tp[v]]) u ^= v ^= u ^= v;
        if(id[u] - id[tp[u]] + 1 <= 2){
            pi res = Query(1, 1, n, id[tp[u]], id[u]);
            if(~res.first) ret.ins(res.first);
            if(~res.second) ret.ins(res.second);
        }
        else ret = ret | query(1, 1, n, id[tp[u]], id[u]);
        u = fa[tp[u]];
    }
    if(id[u] > id[v]) u ^= v ^= u ^= v;
    if(id[v] - id[u] + 1 <= 2){
        pi res = Query(1, 1, n, id[u], id[v]);
        if(~res.first) ret.ins(res.first);
        if(~res.second) ret.ins(res.second);
    }
    else ret = ret | query(1, 1, n, id[u], id[v]);
    return ret;
}
int ans;
int main(){
    read(n);read(m);read(f);
    for (register int i = 1;i <= n;i ++) read(a[i]);
    for (register int i = 1;i < n;i ++){
        int u, v;read(u);read(v);
        add(u, v);add(v, u);
    }
    dfs1(1, 0);dfs2(1, 1);
    build(1, 1, n);
    while(m --){
        ans *= f;
        int k, u, v;
        Bitset ret;read(k);
        while(k --){
            read(u);read(v);u ^= ans, v ^= ans;
            ret = ret | QUERY(u, v);
        }
        int num1 = ret.mex(), num2 = ret.count();
        ans = num1 + num2;
        fprint(num2, 32);fprint(num1, 10);
    }
}