2015
09-17

# Count The Pairs

With the 60th anniversary celebration of Nanjing University of Science and Technology coming soon, the university sets n tourist spots to welcome guests. Of course, Redwood forests in our university and its Orychophragmus violaceus must be recommended as top ten tourist spots, probably the best of all. Some undirected roads are made to connect pairs of tourist spots. For example, from Redwood forests (suppose it’s a) to fountain plaza (suppose it’s b), there may exist an undirected road with its length c. By the way, there is m roads totally here. Accidently, these roads’ length is an integer, and all of them are different. Some of these spots can reach directly or indirectly to some other spots. For guests, they are travelling from tourist spot s to tourist spot t, they can achieve some value f. According to the statistics calculated and recorded by us in last years, We found a strange way to calculate the value f:
From s to t, there may exist lots of different paths, guests will try every one of them. One particular path is consisted of some undirected roads. When they are travelling in this path, they will try to remember the value of longest road in this path. In the end, guests will remember too many longest roads’ value, so he cannot catch them all. But, one thing which guests will keep it in mind is that the minimal number of all these longest values. And value f is exactly the same with the minimal number.
Tom200 will recommend pairs (s, t) (start spot, end spot points pair) to guests. P guests will come to visit our university, and every one of them has a requirement for value f, satisfying f>=t. Tom200 needs your help. For each requirement, how many pairs (s, t) you can offer?

Multiple cases, end with EOF.
First line:n m
n tourist spots ( 1<n<=10000), spots’ index starts from 0.

Next m lines, 3 integers, a b c
From tourist spot a to tourist spot b, its length is c. 0<a, b<n, c(0<c<1000000000), all c are different.

Next one line, 1 integer, p (0<p<=100000)
It means p guests coming.

Next p line, each line one integer, t(0<=t)
The value t you need to consider to satisfy f>=t.

Multiple cases, end with EOF.
First line:n m
n tourist spots ( 1<n<=10000), spots’ index starts from 0.

Next m lines, 3 integers, a b c
From tourist spot a to tourist spot b, its length is c. 0<a, b<n, c(0<c<1000000000), all c are different.

Next one line, 1 integer, p (0<p<=100000)
It means p guests coming.

Next p line, each line one integer, t(0<=t)
The value t you need to consider to satisfy f>=t.

2 1
0 1 2
3
1
2
3
3 3
0 1 2
0 2 4
1 2 5
5
0
2
3
4
5

2
2
0
6
6
4
4
0

#include <iostream>
#include <cstring>
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
#define N 10010
#define M 500500
struct Edge
{
int u,v,w;
}edge[M];
bool cmp(Edge u,Edge v)
{
return u.w<v.w;
}
struct Q
{
int t,idx,val;
Q(int t=0,int idx=0,int val=0)
{
this->t=t;this->idx=idx;this->val=val;
}
}q[N*14];
bool cmp2(Q u,Q v)
{
return u.t<v.t;
}
int n,m,p,fa[N],num[N],ans[N*10];
int _find(int u)
{
return fa[u]==u?u:fa[u]=_find(fa[u]);
}
void update(int f,int val)
{
int left=0,right=p,mid;
while(left<right)
{
mid=left+right>>1;
if(q[mid].t<=f) left=mid+1;
else right=mid;
}
if(q[left].val>f) return;
q[0].val+=val;
q[left].val-=val;
}
int main ()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=0;i<m;++i)
scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
scanf("%d",&p);
for(int i=0;i<p;++i)
{
scanf("%d",&q[i].t);
q[i].idx=i;q[i].val=0;
}
sort(q,q+p,cmp2);
sort(edge,edge+m,cmp);

for(int i=0;i<n;++i) fa[i]=i,num[i]=1;
int cc=0;
for(int i=0;i<m;++i)
{
int u=_find(edge[i].u);
int v=_find(edge[i].v);
if(u==v) continue;
update(edge[i].w,num[u]*num[v]*2);
fa[u]=v;
num[v]+=num[u];

if(++cc>=n-1) break;
}
for(int i=0,k=0;i<p;++i)
{
k+=q[i].val;
q[i].val=k;
}
for(int i=0;i<p;++i) ans[q[i].idx]=q[i].val;
for(int i=0;i<p;++i) printf("%d\n",ans[i]);
}
return 0;
}


1. 这样的文章没删没封，可见你言论还是自由的，你骂中国骂的越厉害，说明你在这还是有人权保障的，当然如果要想让人权保障你也能登上王部长发言的台面，那恐怕还得你自己努力修炼修炼才行

2. 以往认为邓小平行为怪异，且改开暗中有内外两种势力为其护航。最终，目的合二为一。这时候了难到还不知邓是什么身份？！

3. 以往认为邓小平行为怪异，且改开暗中有内外两种势力为其护航。最终，目的合二为一。这时候了难到还不知邓是什么身份？！

4. 以往认为邓小平行为怪异，且改开暗中有内外两种势力为其护航。最终，目的合二为一。这时候了难到还不知邓是什么身份？！

5. 以往认为邓小平行为怪异，且改开暗中有内外两种势力为其护航。最终，目的合二为一。这时候了难到还不知邓是什么身份？！

6. 以往认为邓小平行为怪异，且改开暗中有内外两种势力为其护航。最终，目的合二为一。这时候了难到还不知邓是什么身份？！

7. 以往认为邓小平行为怪异，且改开暗中有内外两种势力为其护航。最终，目的合二为一。这时候了难到还不知邓是什么身份？！

8. 以往认为邓小平行为怪异，且改开暗中有内外两种势力为其护航。最终，目的合二为一。这时候了难到还不知邓是什么身份？！

9. 以往认为邓小平行为怪异，且改开暗中有内外两种势力为其护航。最终，目的合二为一。这时候了难到还不知邓是什么身份？！

10. 以往认为邓小平行为怪异，且改开暗中有内外两种势力为其护航。最终，目的合二为一。这时候了难到还不知邓是什么身份？！

11. 以往认为邓小平行为怪异，且改开暗中有内外两种势力为其护航。最终，目的合二为一。这时候了难到还不知邓是什么身份？！

12. 以往认为邓小平行为怪异，且改开暗中有内外两种势力为其护航。最终，目的合二为一。这时候了难到还不知邓是什么身份？！

13. 以往认为邓小平行为怪异，且改开暗中有内外两种势力为其护航。最终，目的合二为一。这时候了难到还不知邓是什么身份？！

14. 以往认为邓小平行为怪异，且改开暗中有内外两种势力为其护航。最终，目的合二为一。这时候了难到还不知邓是什么身份？！

15. 高仿手表לּKimfoosh(金福祥)Sergio Rossi(塞乔●罗西)Chrome Hearts(克罗心)CONVERSE(匡威)Givenchy(纪梵希)Tommy Hilfiger(汤米)yuandan.gq