xthの旅行--そして集の応用を調べます

説明
卒業して、Xthはとても喜んで、彼がrabbitと二人で旅行に行くためです.彼らは水城ベネチアに来た.周知のように、ここの水路交通はとても発达しているので、xthとrabbitは船で各観光地の间を行き来するしかありません.しかし、rabbitは船酔いして、彼女がつらいのを見て、xthは心が痛いことを知っています.
都市にはnつの観光地があることが知られており、これらの観光地の間にはm本の双方向水路があり、各水路を航行する際にrabbitには「船酔い値」がある.旅行の時、xthはrabbitを連れてできるだけ船酔い値の小さいルートを選んで旅行します.しかしrabbitにも一定の忍耐限界があり、船酔い値が彼女の忍耐度を超えた場合、xthは思い切ってこのルートを放棄することにした.
今xthは何度か質問したいのですが、rabbitの忍耐度を与えて、都市(x,y)間に実行可能な旅行ルートがどれだけ存在するか(x,z)と(z,y)が実行可能であれば(x,y)が実行可能、つまり連通性が伝達可能である)を聞きます.
入力フォーマット
1行目の3つの正の整数n,m,Qは,それぞれ観光地数,水路数,問い合わせ回数を表す.
2行目からm+1行目までの行ごとに3つの正の整数x、y、wは、x番スポットとy番スポットの間に「船酔い値」wの双方向水路があることを示している.
m+2行目からm+Q+1行目までの正の整数kは、問合せで与えられたrabbiの忍耐度がkであることを示す.
出力フォーマット
Q行を共にし、質問ごとに回答する.
サンプル入力Sample Input
5 5 2
1 2 1
2 3 2
3 4 1
4 5 4
5 1 1
1
2
サンプル出力Sample Output
4
10
時間の制限
各試験点1 s
【サンプル説明】
最初の質問:(1,2)、(1,5)、(2,5)、(3,4).ここで(2,5)の具体的な歩き方は,2−1−5である.
2番目の質問:(1,2)、(1,3)、(1,4)、(1,5)、(2,3)、(2,4)、(2,5)、(3,4)、(3,5)、(4,5).そのうち(4,5)の具体的な歩き方は,4−3−2−1−5である.
【データ規模】
20%のデータはn<=20,m<=40,Q<=40を満たす.
40%のデータに対してn<=1000、m<=2000、Q<=1000を満たす.
60%のデータに対してn<=3000、m<=6000、Q<=20000を満たす.
100%のデータに対してn<=10000000,m<=20000000,Q<=20000000を満たす.その他の数は10^9を超えません.
【詳細ヒント】
1与えられたnつの観光地は必ずしも互いに連通しているとは限らず、2つの観光地の間には複数の道路が存在する可能性があり、ある辺がある観光地から彼自身に戻る可能性もある.
2問い合わせの結果が大きい場合がありますので、適切なタイプのストレージを使用することに注意してください.
 
分析:
この問題にとって、質問を処理する順序は実は関係ない.
したがって,質問に対してまずソートを読み込み,さらに小さい順に1つずつ解くことができ,
これなら、一度解いてください.
具体的な点は、2つの接続ブロックを接続するときに、使用してセットを調べます.
2つの連結ブロックを接続し、具体的な集計プロセスはこれ以上説明しない.
セットを調べるときにsum[x]配列を使用します.
xをルートとするインターフェースブロックの合計が存在する道路を記録する.
集中「並」を調べると、
sum[x]:=sum[x]*sum[y]
yの親ノードをxに変更します.

  1 program trip;
  2   var
  3     i,j,n,m,k,l,q,n1,n2,f1,f2:longint;
  4     ans:int64;
  5     a,w,s,e,c,fa,sum:array[0..200000]of longint;
  6     f:array[0..200000]of int64;
  7 
  8   procedure sort(l,r:longint);
  9     var
 10       i,j,x,y:longint;
 11     begin
 12       i:=l;j:=r;
 13       x:=c[(l+r)div 2];
 14       repeat
 15         while c[i]<x do inc(i);
 16         while c[j]>x do dec(j);
 17         if i<=j then
 18           begin
 19             y:=c[i];c[i]:=c[j];c[j]:=y;
 20             y:=s[i];s[i]:=s[j];s[j]:=y;
 21             y:=e[i];e[i]:=e[j];e[j]:=y;
 22             inc(i);dec(j);
 23           end;
 24       until i>j;
 25       if l<j then sort(l,j);
 26       if i<r then sort(i,r);
 27     end;
 28 
 29   procedure qsort(l,r:longint);
 30     var
 31       i,j,x,y:longint;
 32     begin
 33       i:=l;j:=r;
 34       x:=a[(l+r)div 2];
 35       repeat
 36         while a[i]<x do inc(i);
 37         while a[j]>x do dec(j);
 38         if i<=j then
 39           begin
 40             y:=a[i];a[i]:=a[j];a[j]:=y;
 41             y:=w[i];w[i]:=w[j];w[j]:=y;
 42             inc(i);dec(j);
 43           end;
 44       until i>j;
 45       if l<j then qsort(l,j);
 46       if i<r then qsort(i,r);
 47     end;//       
 48 
 49   function getfa(x:longint):longint;
 50     var
 51       i,j:longint;
 52     begin
 53       j:=fa[x];
 54       if fa[j]<>j then fa[x]:=getfa(j);
 55       exit(fa[x]);
 56     end;//     （     ）
 57 
 58   procedure union(x,y:longint);
 59     var
 60       i,j:longint;
 61     begin
 62       fa[y]:=x;
 63     end;//     
 64 
 65   begin
 66     assign(input,'trip.in');
 67     reset(input);
 68     assign(output,'trip.out');
 69     rewrite(output);
 70     readln(n,m,q);
 71     for i:=1 to m do
 72       readln(s[i],e[i],c[i]);
 73     sort(1,m);
 74     for i:=1 to q do
 75       begin
 76         readln(a[i]);
 77         w[i]:=i;
 78       end;
 79     qsort(1,q);
 80     for i:=1 to n do fa[i]:=i;
 81     for i:=1 to n do sum[i]:=1;
 82     n2:=1;
 83     n1:=0;//   
 84     for i:=1 to q do
 85       begin
 86         while (n2<=m)and(c[n2]<=a[i]) do
 87           begin
 88             f1:=getfa(s[n2]);
 89             f2:=getfa(e[n2]);
 90             if f1<>f2 then
 91               begin
 92                 union(f1,f2);
 93                 ans:=ans+sum[f1]*sum[f2];
 94                 sum[f1]:=sum[f1]+sum[f2];
 95               end;
 96             inc(n2);
 97           end;
 98         f[w[i]]:=ans;
 99       end;//        
100     for i:=1 to q do writeln(f[i]);
101     close(input);
102     close(output);
103   end.