题目
给定一棵n个点的边权为0或1的树，一条合法的路径(x,y)(x≠y)满足，从x走到y，一旦经过边权为1的边，就不能再经过边权为0的边，求有多少边满足条件？ 提交地址
题解
合法路径只有三种情况：全为
0
0
0，全为
1
1
1，先
0
0
0后
1
1
1我们可以将
0
0
0和
1
1
1分为不同的连通块，那么同一连通块内的答案显然是
s
i
z
×
(
s
i
z
−
1
)
siz\times(siz-1)
siz×(siz−1)对于先0后一的路径显然存在一个
t
t
t使得
(
x
,
t
)
(x,t)
(x,t)全0，
(
t
,
y
)
(t,y)
(t,y)全1答案为
(
s
i
z
−
1
)
×
(
s
i
z
′
−
1
)
(siz-1)\times(siz'-1)
(siz−1)×(siz′−1)
code
#include <bits/stdc++.h>
using namespace std
;
template <class T> inline void read(T
&s
) {
s
= 0; T w
= 1, ch
= getchar();
while (!isdigit(ch
)) { if (ch
== '-') w
= - 1; ch
= getchar(); }
while (isdigit(ch
)) { s
= (s
<< 1) + (s
<< 3) + (ch
^ 48); ch
= getchar(); }
s
*= w
;
}
typedef long long LL
;
const int N
= 2e5 + 100;
int n
, tot
;
int f
[2][N
], siz
[2][N
];
inline int find(int id
, int x
) {
return x
== f
[id
][x
] ? x
: f
[id
][x
] = find(id
, f
[id
][x
]);
}
inline void merge(int id
, int x
, int y
) {
int fx
= find(id
, x
), fy
= find(id
, y
);
if (fx
== fy
) return ;
f
[id
][fx
] = fy
;
siz
[id
][fy
] += siz
[id
][fx
];
}
int main() {
read(n
);
for (int i
= 1; i
<= n
; ++i
) {
f
[0][i
] = i
, f
[1][i
] = i
;
siz
[0][i
] = 1, siz
[1][i
] = 1;
}
for (int i
= 1; i
< n
; ++i
) {
int x
, y
, z
; read(x
), read(y
), read(z
);
merge(z
, x
, y
);
}
LL ans
= 0;
for (int i
= 1; i
<= n
; ++i
) {
if (f
[0][i
] == i
)
ans
+= 1ll * siz
[0][i
] * (siz
[0][i
] - 1);
if (f
[1][i
] == i
)
ans
+= (LL
)1ll * siz
[1][i
] * (siz
[1][i
] - 1);
int x
= find(0, i
), y
= find(1, i
);
ans
+= 1ll * (siz
[0][x
] - 1) * (siz
[1][y
] - 1);
}
printf("%lld\n", ans
);
return 0;
}
