题目大意
有一棵个
n
n
n
点的树，每条边有边权，定义
f
i
,
j
f_{i,j}
f
i
,
j
为点
i
i
i
到点
j
j
j
的路径上所有边的边权的按位与(
&
值)，
g
i
,
j
g_{i,j}
g
i
,
j
为点
i
i
i
到点
j
j
j
的路径上所有边的边权的按位或(
|
值)，求
∑
i
=
1
n
∑
j
=
i
+
1
n
f
i
,
j
×
g
i
,
j
\sum_{i=1}^{n} \sum_{j=i+1}^{n} f_{i,j} \times g_{i,j}
∑
i
=
1
n
∑
j
=
i
+
1
n
f
i
,
j
×
g
i
,
j
模
998244353
998244353
9
9
8
2
4
4
3
5
3
的值。
解题思路
首先看到按位或和按位与和这毒瘤的数据范围，就可以想到只能用
二
进
制
\color{red}二进制
二
进
制
来解。
类似于这道题
→
\to
→
奇怪的最短路
题面
给定长度为
nn
n
的数列
aa
a
，如果
ai
a
n
d
a
j
!
=
0
a_i \ and \ a_j != 0
a
i
a
n
d
a
j
!
=
0
（按位与），则在
ii
i
，
jj
j
之间存在一条长度为
ai
+
a
j
a_i + a_j
a
i
+
a
j
的边，求
11
1
至所有点的最短路。
普及一下：
按位与运算（
a
n
d
and
a
n
d
）
定义：参加运算的两个数据，按二进制位进行”与”运算。
运算规则：
0&0=0 ，0&1=0 ，1&0=0 ，1&1=1
总结：两位同时为
1
1
1
，结果才为
1
1
1
，否则结果为
0
0
0
。
例如：
3
a
n
d
5
3 \ and \ 5
3
a
n
d
5
即
0000 0011 & 0000 0101 = 0000 0001
，因此
3
a
n
d
5
3 \ and \ 5
3
a
n
d
5
的值得
1
1
1
。
按位或运算符（
o
r
or
o
r
）
定义：参加运算的两个对象，按二进制位进行”或”运算。
运算规则：
0|0=0 ，0|1=1 ，1|0=1 ，1|1=1
总结：参加运算的两个对象只要有一个为
1
1
1
，其值为
1
1
1
。
例如：
3
o
r
5
3 \ or \ 5
3
o
r
5
即
0000 0011 | 0000 0101 = 0000 0111
，因此，
3
o
r
5
3 \ or \ 5
3
o
r
5
的值得
7
7
7
。
对于二进制，首先想到的就是
拆
位
\color{red}拆位
拆
位
。
类似于乘法分配律，我们可以枚举第
i
i
i
位和 第
j
j
j
位，计算有多少对
x
,
y
x,y
x
,
y
满足
f
x
,
y
f_{x,y}
f
x
,
y
的第
i
i
i
位和
f
x
,
y
f_{x,y}
f
x
,
y
的第
j
j
j
位都为
1
1
1
，那么答案即为
x
,
y
x,y
x
,
y
的对数乘上
2
i
+
j
2^{i+j}
2
i
+
j
。
先看第
i
i
i
位为
1
1
1
的
f
x
,
y
f_{x,y}
f
x
,
y
，因为我们希望最后按位与得到的结果第
i
i
i
位为
1
1
1
，那么路径上的边权第
i
i
i
位一定都是
1
1
1
。所以我们只保留边权的第
i
i
i
位为
1
1
1
的边，那么在每个连通块内的任意两点
<
u
,
v
>
<u,v>
<
u
,
v
>
满足
f
u
,
v
f_{u,v}
f
u
,
v
的第
i
i
i
位为
1
1
1
，用并查集维护即可。
再看第
j
j
j
位为
1
1
1
的
g
x
,
y
g_{x,y}
g
x
,
y
的个数，显然，这很难求，因为
o
r
or
o
r
运算不好处理为
1
1
1
的情况，那就需要处理为
0
0
0
的情况。
根据
容
斥
原
理
\color{red}容斥原理
容
斥
原
理
，易得
f
x
,
y
f_{x,y}
f
x
,
y
第
i
i
i
位和
g
x
,
y
g_{x,y}
g
x
,
y
第
j
j
j
位都为
1
1
1
的情况数
=
=
=
f
x
,
y
f_{x,y}
f
x
,
y
第
i
i
i
位为
1
1
1
的情况数
−
–
−
f
x
,
y
f_{x,y}
f
x
,
y
第
i
i
i
位为
1
1
1
，
g
x
,
y
g_{x,y}
g
x
,
y
第
j
j
j
位为
0
0
0
的情况数。
十
年
O
I
一
场
空
，
不
开
l
o
n
g
l
o
n
g
见
祖
宗
\color{red}{十年 \ OI \ 一场空，不开 \ long \ long \ 见祖宗}
十
年
O
I
一
场
空
，
不
开
l
o
n
g
l
o
n
g
见
祖
宗
AC CODE
快读终于缩短了，祭
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define _ (int) 5e4 + 5
#define MOD 998244353
struct Fastio
{
template <typename T>
inline Fastio operator>>(T &x)
{
x = 0;
char c = getchar();
while (c < '0' || c > '9')
c = getchar();
while (c >= '0' && c <= '9')
x = (x << 3) + (x << 1) + (c ^ 48), c = getchar();
return *this;
}
template <typename T>
inline Fastio &operator<<(T x)
{
if (x == 0)
{
putchar('0');
return *this;
}
if (x < 0) putchar('-'), x = -x;
static int sta[45];
int top = 0;
while (x) sta[++top] = x % 10, x /= 10;
while (top) putchar(sta[top] + '0'), --top;
return *this;
}
} oi;
int n, ans;
int u[_], v[_], w[_];
int fa[_], siz[_];
void init()
{
for (int i = 1; i <= n; i++)
{
fa[i] = i;
siz[i] = 1;
}
}
int find(int x)
{
return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
x = find(x), y = find(y);
if (x != y)
{
fa[y] = x;
siz[x] += siz[y];
}
}
signed main()
{
oi >> n;
for (int i = 1; i < n; ++i) oi >> u[i] >> v[i] >> w[i];
for (int i = 0; i <= 20; i++)
{
for (int j = 0; j <= 20; j++)
{
int cnt1 = 0, cnt2 = 0;
init();
for (int k = 1; k < n; k++)
if (w[k] & (1 << i)) // 第 i 位和第 j 位都为 1 的
{
merge(u[k], v[k]);
}
for (int k = 1; k <= n; k++)
if (k == find(k))
{
cnt1 = (cnt1 + (siz[k] - 1) * siz[k] / 2 % MOD) % MOD;
}
init();
for (int k = 1; k < n; k++)
if (w[k] & (1 << i))
{
if (!(w[k] & (1 << j))) // 第 i 位为 1，第 j 位为 0 的
{
merge(u[k], v[k]);
}
}
for (int k = 1; k <= n; k++)
if (k == find(k))
{
cnt2 = (cnt2 + (siz[k] - 1) * siz[k] / 2 % MOD) % MOD;
}
ans = (ans + (1ll << (i + j)) % MOD * (cnt1 - cnt2 + MOD) % MOD) % MOD;
}
}
oi << ans;
return 0;
}