2021牛客多校第四场题解

E题

题目大意：给出n个点，每个点的点权取值范围[ L[i] , R[i] ]；给出n-1条边，边的边权w表示连接的两个点的点权的异或值为w。问合法的取值有多少套。

思路：假设确定了第一个点的值，那么其他所有点的值就确定下来了。不妨令第一个点的初始值为0，此时所有点初始值被定好。设第一个点最终值为a，第i个点初始值为x，而第i个点的最终值要满足L[i] <= (x xor a）<= R[i]，即a要满足 (L[i] xor x) <= a <= (R[i] xor x)，而我们知道区间异或某个数后不一定连续，考虑线段树维护0 ~ (1<<30)-1的区间，每次二分都能得到类似 01000~01111的区间（形式为满足前k位相同，后m位填满000 ~ 111），每次判断由该二分区间异或x后是否落在L[i] , R[i]里，若不在标记不可用。最后用整个区间长度1<<30减去不可用的区间长度即为答案。

ac代码：

#include <bits/stdc++.h>

using namespace std;

const int N = 6e6+6;

int n,root = 1,cnt = 1;
int ch[N][2],sum[N];
bool tag[N];
int e[N],ne[N],idx,W[N],h[N];
int l[N],r[N];

void add(int a,int b,int c){
    e[idx] = b,ne[idx] = h[a],W[idx] = c,h[a] = idx++;
}

void build(int &rt,int l,int r,int x,int y,int w){
    int len = r - l + 1;
    int l1 = l ^ (w & (~(len - 1)));
    int r1 = l1 + len - 1;
    if(!rt)rt = ++cnt;
    if(r1<=y&&l1>=x)return ;
    if(r1<x||l1>y){
        sum[rt] = len;
        tag[rt] = 1;
        return ;
    }
    int mid = l + r >> 1;
    build(ch[rt][0],l,mid,x,y,w);
    build(ch[rt][1],mid+1,r,x,y,w);
    if(tag[rt])sum[rt] = len;
    else sum[rt] = sum[ch[rt][0]] + sum[ch[rt][1]];
}

void dfs(int u,int f,int w){
    build(root,0,(1<<30) - 1,l[u],r[u],w);
    for(int i = h[u];i != -1;i = ne[i]){
        int j = e[i];
        if(j == f)continue;
        dfs(j,u,w^W[i]);
    }
}

int main(){
    cin >> n;
    memset(h,-1,sizeof h);
    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;
        add(u,v,w),add(v,u,w);
    }
    dfs(1,-1,0);
    cout << (1 << 30) - sum[1] << endl;
    return 0;
}

p.s. dfs的时候里面注意是w ^ W[i]而不是w ^ W[j] 。N开大一点。
动态开点经验++