牛客 - Tree Xor

传送门：牛客 - Tree Xor

思路分析

显然，如果确定了一个点的权值，那么其他点的权值都能确定。
定$1$为根，$dfs$一遍路径异或和就能得到所有$w[1] \oplus w[i]$的值。
令$d[i] = w[1] \oplus w[i]$，$w[1] = a$，那么将得到$n$个集合关系
$a \in \lbrace x\oplus d[i]\mid l[i]\leq x \leq r[i] \rbrace $
$a$的取值个数就是$n$个集合取并集，难点在于如何求一个区间$[l,r] \oplus k$之后的$log(k)$段区间。
值域为$[0,2^{30}-1]$的值域线段树有一个很好的性质，它的每一个完整的区间，高位都是相等的，低位是$[0,11111]$，显然$[0,11111]\oplus ????? $之后的值域也是$[0,11111]$，所以就可以很容易找到区间$[l,r] \oplus k$之后的$log(k)$段区间，然后在线段树上对这$log(k)$段区间进行修改。
答案为并集或者全集减去不合法的区间，后者比较好写，直接区间覆盖就行了，代码也是这个。

AC代码

#include <bits/stdc++.h>
#define V vector
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define lowbit(x) (x)&(-x)
#define sz(x) (int)(x).size()
#define each(x,a) for(auto& x:a)
#define all(x) (x).begin(),(x).end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef unsigned long long ull;

const int INF = 0x3f3f3f3f;
const double PI = acos(-1);
const int N = 1e5+10;
const int M = (1<<30) - 1;

struct node{
    int l,r,sum;

    void clear(){
        l = r = sum = 0;
    }
}tree[N*30];

int cnt,root;

#define ls(x) tree[x].l
#define rs(x) tree[x].r

void pp(int x){
    tree[x].sum = tree[ls(x)].sum+tree[rs(x)].sum;
}

int newnode(){
    ++cnt;
    tree[cnt].clear();
    return cnt;
}

void modify(int &x,int l,int r,int ql,int qr){
    if(!x) x = newnode();
    if(tree[x].sum == r-l+1) return ;
    if(ql<=l && r<=qr){
        tree[x].sum = r-l+1;
      
        return ;
    }
    int mid = (l+r)/2;
    if(ql<=mid) modify(ls(x),l,mid,ql,qr);
    if(qr>mid) modify(rs(x),mid+1,r,ql,qr);
    pp(x);
}


int l[N],r[N],d[N];
vector<pii>e[N];

void dfs(int u,int f,int val){
    d[u] = val;
    for(auto x:e[u]){
        int v = x.fi;
        int w = x.se;
        if(v == f) continue;
        dfs(v,u,val^w);
    }
}

void solve(int l,int r,int ql,int qr,int k,int w,int dep){
    if(ql<=l && r<=qr){
        int mi = w;
        int ma = (1<<(dep+1))-1+mi;
        modify(root,0,M,mi,ma);
        return;
    }
    int mid = (l+r)/2;
    int s = (k>>dep)&1;
    if(ql<=mid) solve(l,mid,ql,qr,k,(w|(s<<dep)),dep-1);
    if(qr>mid) {
        if(!s) solve(mid+1,r,ql,qr,k,(w|(1<<dep)),dep-1);
        else solve(mid+1,r,ql,qr,k,w,dep-1);
    }
}

signed main() {

#ifdef xiaofan
    clock_t stTime = clock();
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
/*==========================begin============================*/
    IOS;
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>l[i]>>r[i];
    for(int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].pb(mp(v,w));
        e[v].pb(mp(u,w));
    }
    dfs(1,1,0);
    for(int i=1;i<=n;i++){
        if(l[i]) solve(0,M,0,l[i]-1,d[i],0,29);
        if(r[i]+1<=M) solve(0,M,r[i]+1,M,d[i],0,29);
    }
    cout<<M+1-tree[root].sum<<endl;




/*===========================end=============================*/
#ifdef xiaofan
    cerr << "Time Used:" << clock() - stTime << "ms" <<endl;
#endif
    return 0;
}