链接
https://ac.nowcoder.com/acm/contest/11255/E
题意
$n$ 个节点的树，第 $i$ 个点的权值为 $w_i$。
但是目前只知道 $w_i$ 是 $[l_i,r_i]$ 内的一个整数和每条边 $(u,v)$ 的 $w_u\oplus w_v$ 的值。
给 $w_i$ 赋值，求方案数。
思路
因为每条边的权值是确定的，所以当根节点的权值确定时，每个点的权值也都确定了。
不妨设根节点为 $1$，根节点权值为 $0$，计算出其他节点的权值，记根节点权值为 $0$ 时，点 $i$ 的权值为 $a_i$。
那么 $w_i\in {l_i\le w_i\oplus a_i \le r_i}$，因此答案就是对 $w_{1\sim n}$ 的取值取交集。
接下来考虑 $w_i$ 的取值，先看一个例子：$(1010)_2\oplus x\in[0,(1100100)_2]$
把 $[(0)_2,(1100100)_2]$ 分成
$[(0)_2,(111111)_2]$，$x\in[(0)_2,(111111)_2]$
$[(1000000)_2,(1011111)_2]$，$x\in[(1000000)_2,(1011111)_2]$
$[(1100000)_2,(1100011)_2]$，$x\in[(1001000)_2,(1001011)_2]$
$[(1100100)_2,(1100100)_2]$，$x\in[(1101110)_2,(1101110)_2]$
从上述例子可以看出 我们可以把 $[0,r]$ 分成若干个 $[(b_1b_2\dots b_k00\dots0)_2,(b_1b_2\dots b_k11\dots1)_2]$ 的区间，这样 $x$ 的 $k$ 位后可以任意取值，而前 $k$ 位是确定的。
对于 $[l_i,r_i]$，可以分成 $[0,l_i-1]$ 和 $[0,r_i]$ 两个区间考虑，利用差分思想计算覆盖次数为 $n$ 的区间长度和。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <bits/stdc++.h>
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
using namespace std;
typedef double DB;
typedef long double LD;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VPII;
const int N=1e5+5;
int w[N],l[N],r[N];
VPII g[N],o;
void solve(int u,int r,int x) {
if(r<0) return;
int l=0;
for(int i=29;~i;i--) if(r>=1<<i) {
int d=((w[u]>>i)^(l>>i))<<i;
o.EB(d,x);
o.EB(d+(1<<i),-x);
l+=1<<i;
r-=1<<i;
}
o.EB(l^w[u],x);
o.EB((l^w[u])+1,-x);
}
void dfs(int u,int fa) {
solve(u,l[u]-1,-1);
solve(u,r[u],1);
for(auto x:g[u]) {
int v=x.FI;
if(v==fa) continue;
w[v]=w[u]^x.SE;
dfs(v,u);
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
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;
g[u].EB(v,w);
g[v].EB(u,w);
}
dfs(1,0);
sort(ALL(o));
int res=0,len=0,pre=o[0].FI;
for(auto x:o) {
if(x.FI!=pre&&len==n) res+=x.FI-pre;
len+=x.SE;
pre=x.FI;
}
cout<<res<<'\n';
return 0;
}
|