- 利用线段树划分区间【l,r】
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int l[100005],r[100005],w[100005];
vector<int>a[100005],c[100005];
vector<pair<int,int> >ans;
void ask(int l,int r,int u,int v,int id)
{
if(u<=l&&v>=r)
{
int len=r-l+1;
int val=(w[id]&(~(len-1)));
l=l^val;
r=r^val;
ans.push_back(make_pair(l,1));
ans.push_back(make_pair(r+1,-1));
return;
}
int mid=(l+r)>>1;
if(u<=mid)
{
ask(l,mid,u,v,id);
}
if(v>mid)
{
ask(mid+1,r,u,v,id);
}
}
void dfs(int n1,int fa)
{
for(int i=0;i<a[n1].size();i++)
{
if(a[n1][i]!=fa)
{
w[a[n1][i]]=w[n1]^c[n1][i];
dfs(a[n1][i],n1);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
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;
a[u].push_back(v);
a[v].push_back(u);
c[u].push_back(w);
c[v].push_back(w);
}
dfs(1,0);
for(int i=1;i<=n;i++)
{
ask(0,(1<<30)-1,l[i],r[i],i);
}
sort(ans.begin(),ans.end());
int cur=0,la=0,res=0;
for(int i=0;i<ans.size();i++)
{
if(cur==n)
{
res=res+ans[i].first-la;
}
cur=cur+ans[i].second;
la=ans[i].first;
}
cout<<res<<endl;
return 0;
}