2021牛客暑期多校训练营4 E、Tree Xor

题目大意

你有一个一颗树节点数，树上的边有一个边权，点有一个点权，你要保证有直接父子关系的点之间，并且树上每个点他的点权选取范围为，现在请问你能构造出多少颗不同的树，有任何一个不同就认为是一颗不同的树。

Solution

考点：线段树区间性质

首先树上边权关系给你了，所以当我们顶下后整棵树后续的都会被确定下来，问题就转化成有多少种取值可能。

好，下面我们假设求一遍，这样就可以预处理出每个点的，我们就可以把题目的区间变成下面的形式。

那么全部已知，问题就变成了个区间求并集的问题，并集的大小就是答案了。

但是由于是异或操作，所以本身连续的在异或之后整个区间并不会保持连续，下面我们就要想办法处理出这些分散的区间来。

然后就要想到这个题目的难点了，用线段树的区间性质考虑新建区间，因为线段树最多会分成段区间，并且每段区间都有很明显的前后一致的相关性，那么我们就在线段树上找到这些被包含的区间，然后把他们处理好之后塞进容器里面，最终求解有没有某些部分是个区间相同的并集，这个用一次扫描线即可。

借用一下这位大佬(lalalzo)的图，原文链接点这里

const int N = 1e5 + 7;
ll n, m;
pai p[N];
vector<pai> G[N];
int a[N];

void dfs(int u, int fa) {
    for (auto& [v, w] : G[u]) {
        if (v == fa)    continue;
        a[v] = a[u] ^ w;
        dfs(v, u);
    }
}

vector<pai> seg;
int bit[40];
#define mid (l + r >> 1)
void build(int l, int r, int cnt, int L, int R, int val) {
    if (L <= l && r <= R) {
        int ql = (l ^ val) & bit[cnt];
        int qr = ql + (1 << cnt) - 1;
        seg.push_back({ ql,qr });
        return;
    }
    if (L <= mid)    build(l, mid, cnt - 1, L, R, val);
    if (R > mid)    build(mid + 1, r, cnt - 1, L, R, val);
}

int solve() {
    bit[0] = (1 << 30) - 1;
    for (int i = 1; i <= 30; ++i) {
        bit[i] = bit[i - 1] ^ (1 << (i - 1));
    }
    n = read();
    for (int i = 1; i <= n; ++i)    p[i] = { read(), read() };
    int u, v, w;
    for (int i = 2; i <= n; ++i) {
        u = read(), v = read(), w = read();
        G[u].push_back({ v,w });
        G[v].push_back({ u,w });
    }
    dfs(1, 0);
    for (int i = 1; i <= n; ++i) {
        build(0, bit[0], 30, p[i].first, p[i].second, a[i]);
    }
    vector<pai> all;
    for (auto& [l, r] : seg) { // 扫描线
        all.push_back({ l,1 });
        all.push_back({ r + 1,-1 });
    }
    sort(all.begin(), all.end());
    int res = 0, tag = 0;
    for (int i = 0; i < all.size(); ++i) {
        tag += all[i].second;
        if (tag == n) {
            res += all[i + 1].first - all[i].first;
        }
    }
    print(res);


    return 1;
}