[USACO 18 JAN]MooTube【調査集】

Description
Inberhis spare time,Farmer John has created a new video-shring service,which he names MooTube.On MooTube,Farmer John’s cows can recorded,share,and discover manys videose.Histows Codeve 1FJ J.can’t quite figure out how to help his cows find new videos they might like.FJ wants to create a list of「suggggested videos」forevryMooTube video.This way,cowwwill be recococococococococococococococowbe recocococococococococococococococococococococococococommbe reremimimimimimimimimimimimimimimimimimimindbe remimimimimimimimidedededededededededededededededededededededededededededename sugges,how relevant two videos are to each other.He picks N−1 pairs of videos and manaually computtes their pair wise relevance.The n,FJ visualizes videos as a network,where each vides therity and and on on on 1FJ has picked his N−1 pairs so ththat any video can be reached ffrom any othe video along a path of connects inininineeexactlyoneway.FJ decides ththat the relevancnce of any pair to of videdeoooooooooooovidedededededededededemomomomomoproproproproproproproproproproproproconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconconany given MooTube video、all other videos with relevance at least K to that video will be suggated.However、FJ is woried that too manny videos will be suggated to his cows、which could distract them from milk production!The refore、he wants to carefully set an apprate value of K.Farmer John would like your help answeng a number of questions about the suggated videos for certain values of K.
Input
The first line of input contains N and Q(1≦Q≦100,000).The next N−1 line each describe a pair of videos FJ manualy compres.Each line includes three integers pi,qi,and i(1,pi,qi)≦1indicadidicating ththat video s pi and qi arconnected with relevancri. The nexs Q lins describe Farmer John's Q questitititins.Each line containtstststststwowointegers、ki and vi(1≦ki≦1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,1≦viininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininininin=キ.
Output
Output Q line.On line.Output the answer to FJ’s ith question.
Sample Input
4 3 1 2 3 3 2 2 2 4 1 2 4 1 2 4 1 1 3 1
Sample Output
3 0 2
N個の音楽があり、N−1対の音楽の関連度(長さ)を与え、任意の2つの音楽が連結可能になり、いずれかの2つの音楽の関連度は2つの音楽間の経路長の最小値となる.M個の問い合わせがありますが、各問い合わせはki、viです.viとの関連度がkiに等しい点がいくつあるかを求めます.サンプル解釈:
u−−−v=>w 1−−−2=>31−−3=>21−−−4=>32−−−−3=>22−−−−−4=>43−4=>2
作り方:各辺をwの大きさから小順に並べ、各問い合わせのkiは大きいから小さい順に並べ替えて(保留位置)、そして問い合わせのkiに対してすべての辺でw>=kiの辺を見つけて、これらの辺の端点を合併して調べて、各集の下にいくつの点があるかを記録して、この質問の答えans = num[i]-1の所在を更新して、集の点数-1を調べます.そして答えを出力します.

#include
#include
#include
using namespace std;
typedef long long ll;
const int MAXN = 100000 + 5;
struct node {
    int u, v, w;
    node() {}
    node(int W) { w = W; u = v = 0; }
    bool operatorx) {
        if (w == x.w) {
            return u > x.u;
        }
        return w > x.w;
    }
}ed[MAXN];// 
struct qu {
    int id, v, k, ans;
    bool operatorx) {
        return k > x.k;
    }
}q[MAXN];//  
int st[MAXN];//   
int num[MAXN];//          
int findf(int x)
{
    if (st[x] == x)
        return x;
    return st[x]=findf(st[x]);
}
void merge(int a, int b)
{
    num[findf(a)] += num[findf(b)];
    st[findf(b)] = findf(a);
}
bool vmp(qu x, qu y)
{
    return x.id < y.id;
}
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < MAXN; i++)
    {
        st[i] = i;
        num[i] = 1;
    }
    for (int i = 0; i < n-1; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        if (u > v)
            swap(v, u);
        ed[i].u = u;
        ed[i].v = v;
        ed[i].w = w;
    }
    sort(ed, ed + n);
    for (int i = 0; i < m; i++)
    {
        scanf("%d%d", &q[i].k, &q[i].v);
        q[i].id = i;
    }
    sort(q, q + m);
    int j = 0;
    for (int i = 0; i < m; i++)
    {
        while (ed[j].w >= q[i].k)
        {
            int u = ed[j].u;
            int v = ed[j].v;
            if (findf(u) != findf(v))
            {
                merge(u, v);
            }
            j++;
        }
        q[i].ans = num[findf(q[i].v)] - 1;
    }
    sort(q, q + m,vmp);
    for (int i = 0; i < m; i++)
    {
        printf("%d
", q[i].ans);
    }
}