B.“提莫队长正在待命！”（并查集求连通块）

Description

迅捷斥候·提莫作为班德尔城安全的侦察兵首领，也是班德尔城最富盛名的特种部队之一“主舰斥候队”一员，平时他会在各处巡逻保证班德尔城的安危。

我们现在可以把班德尔城看做由nn个小城镇组成的大城市，在这nn个城市之间有n-1n−1条道路将这nn个小城镇连接起来（也就是说这nn个小城镇形成了一个树形的结构）。

由于城镇太多，提莫一个人无法把所有的城镇巡逻到，所以他会在某些道路上种上蘑菇，这样如果有敌人入侵在前进的路上就会被蘑菇炸伤。

现在提莫想知道如果按照他现在放蘑菇的方式，敌人经过哪些路径会被蘑菇炸伤，输出路径数。

ps：路径(uu,vv)是指从城镇uu走到城镇vv所要走过的边。

Input

第一行一个整数nn，代表小城镇的个数。

接下来n-1n−1行，每行有33个整数u,v,wu,v,w。

代表城镇uu到城镇vv之间有一条道路，如果ww = 11，则表示提莫在这条道路上放了蘑菇，否则就没有。

数据范围：

1\leq n\leq 3000001≤n≤300000
1\leq u,v\leq n1≤u,v≤n
w = 1;or;0w=1or0

Output

输出一行，代表答案。

Sample Input 1

4
1 2 1
3 1 0
1 4 1
Sample Output 1

10
Hint

这10条路径分别为：

(1,2),(2,1),(1,4),(4,1),(2,3),(3,2),(2,4),(4,2),(3,4),(4,3)

Source

2019年集训队选拔赛

思路：把都是0的并起来求没有炸弹的路径，那么剩下的就是有炸弹的路径。
而一个树的总路径数位$n\ast (n-1)$（任意两点间的路径唯一）

#include
#include
using namespace std;const int MAXN = 300000 + 10;#define ll long longll pa[MAXN];
ll num[MAXN];         
int findset(ll x)
{if(pa[x]==x)return x;return findset(pa[x]);
}void bind(ll i,ll j)
{ll fa = findset(i);ll fb = findset(j);if(fa!=fb){pa[fa]=fb;num[fb] += num[fa];num[fa] = 0;}
}int main()
{ll n;while(scanf("%lld",&n)==1){ll x,y,w;for(ll i=1;i<=n;i++){pa[i]=i;num[i] = 1;}for(ll i = 0;i<n - 1;i++){scanf("%lld%lld%lld",&x,&y,&w);if(w == 0){bind(x,y);//bind(y,x);}}ll ans = 0;for(ll i = 1;i<=n;i++){ans+=num[i] * (num[i] - 1);}	printf("%lld\n",n * (n - 1) - ans);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！