Tree Xor

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int M = (1<<30)-1;
const int N = 100005;
int num,to[N<<1],nxt[N<<1],head[N],co[N<<1];
int L[N],R[N],a[N];
int n;
void add(int u,int v,int w)
{
    ++num;
    nxt[num]=head[u];
    to[num]=v; co[num]=w;
    head[u]=num;
}
void tr_dfs(int x,int pre,int v)
{
    a[x]=v;
    for (int e=head[x];e;e=nxt[e]) if (to[e]!=pre)
        tr_dfs(to[e],x,v^co[e]);
}
int tr[N*60],lc[N*60],rc[N*60]; 
int nodecnt=0,rt=0;
int ans=0;
void modify(int&p,int l,int r,int ql,int qr,int val,int i){
    if(r<ql||l>qr)return;
    if(!p)p=++nodecnt;
    if(ql<=l&&qr>=r){
        tr[p]++;
        return;
    }
    int mid=(l+r)>>1;
    if((val>>i)&1){
        modify(lc[p],mid+1,r,ql,qr,val,i-1);modify(rc[p],l,mid,ql,qr,val,i-1);
    }else{
        modify(lc[p],l,mid,ql,qr,val,i-1);modify(rc[p],mid+1,r,ql,qr,val,i-1);        
    }
}
int que(int x,int l,int r,int cnt){
    if(!x)return 0;
    cnt+=tr[x];
    if(cnt==n){
        return r-l+1;
    }
    int mid=(l+r)>>1;
    return que(lc[x],l,mid,cnt)+que(rc[x],mid+1,r,cnt);
}
int main()
{
    cin>>n;
    for (int i=1;i<=n;++i) scanf("%d%d",&L[i],&R[i]);
    for (int i=1,u,v,w;i<n;++i) scanf("%d%d%d",&u,&v,&w),add(u,v,w),add(v,u,w);
    tr_dfs(1,0,0);
    for(int i=1;i<=n;i++)modify(rt,0,M,L[i],R[i],a[i],29);
    cout<<que(rt,0,M,0)<<endl;
    return 0;
}

Sample Game

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
const int N=1e2+5;
ll dp[N],f[N],w[N],p[N],sum[N],num[N];
ll n,s;
ll pow(ll a,ll b)
{
    ll ret=1;
    while(b)
    {
        if(b&1)
            ret=ret*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ret;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&w[i]);
        s+=w[i];
    }
    for(int i=1;i<=n;i++)
        p[i]=pow(s,mod-2)*w[i]%mod;
    num[n]=0;
    for(int i=n;i>=1;i--){
        f[i]=(1+num[i])*pow(1-p[i]+mod,mod-2)%mod;
        num[i-1]=(num[i]+p[i]*f[i]%mod)%mod;
    }
    num[n]=0;
    long long ans=0;
    for(int i=n;i>=1;i--){
        dp[i]=(1+2*p[i]*f[i]%mod+num[i])%mod*pow(1-p[i]+mod,mod-2)%mod;
        num[i-1]=(num[i]+p[i]*(dp[i]+2*f[i])%mod)%mod;
        ans=(ans+p[i]*(dp[i]+2*f[i])%mod)%mod;
    }
    ans=(ans+1)%mod;
    cout<<ans<<endl;
    return 0;
}