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，则表示提莫在这条道路上放了蘑菇，否则就没有。

数据范围：

1leq nleq 3000001≤n≤300000
1leq u,vleq 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的并起来求没有炸弹的路径，那么剩下的就是有炸弹的路径。

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

#define ll long long
const ll maxn = 1000000 + 10;

ll T;
ll n;
ll c[maxn];
ll sum[maxn];
bool is_prime[maxn];
ll yinzi[maxn];
ll cnt;
ll ans[maxn];

void Add(ll x,ll y)
{
	for ( ; x <= maxn && x; x += x & -x )
		c[x] += y;
}
int Summ(ll x)
{
	int ans = 0;
	for ( ; x; x -= x & -x )
		ans += c[x];
	return ans;
}

void isprime()
{
	ll i,j;
	memset(is_prime,true,sizeof(is_prime));
	memset(yinzi,0,sizeof(yinzi));
	yinzi[1] = 1;
	cnt = 0;

	for(i=2;i<=maxn;i++)
	{
		if(is_prime[i])
		{	
			yinzi[i] = i;
			for(j=i+i;j<=maxn;j+=i)
			{
				is_prime[j]=false;
				if(yinzi[j]==0)
				{
					yinzi[j] = i;
				}
			}
		}
	}

}

void init()
{
	memset(c,0,sizeof(c));
	for(ll i = 2;i<=maxn;i++)
	{
		for(ll j=1;j<i;j++)
		{
			if(yinzi[i] >= yinzi[j])
			Add(i,1);
		}
		ans[i] = Summ(i) - Summ(i - 1);
	}
}

void init2()
{
	memset(c,0,sizeof(c));
	memset(yinzi,0,sizeof(yinzi));
	yinzi[1] = 1;
	for(int i = 2;i<=maxn;i++)
	{
		for(int j = i;j<=maxn;j += i)
		{
			if(!yinzi[j])
				yinzi[j] = i;
		}
	}
	for(int i = 1;i<=maxn;i++)
	{
		ans[i] = Summ(yinzi[i]); 
		Add(yinzi[i],1);
	}
	
}

int main()
{
//	isprime();
//	memset(c,0,sizeof(c));
//	memset(yinzi,0,sizeof(yinzi));
	init2();
	scanf("%lld",&T);

	while(T--)
	{
		ll n;
		scanf("%lld",&n);
//		ans[2] = 2;
		printf("%lld
",ans[n]);
	}
	return 0;
}