hdu 5102 The K-th Distance （队列+生成法，，）

题意：

N个点的一棵树。定义点u和点v的距离等于它们之间的路径（唯一的）的长度。这样我们可以得到n*(n-1)/2个距离。

将它们从小到大排序，问前K个数的和是多少。

思路：

将边长为1的树枝都入队列。每次取出一个，然后从这根树枝的前端生出一个新点，变成距离加1的一根新树枝，将其入队列。如此操作下去。

可得到所有的各种长度的树枝。因为每根树枝其实有两个在队列里（互为反方向生长），故求前2*K个数的和，然后除以2。

*：我们取前队列里的前2K个，就算后面的若干些不是一对一对的，也一定可以取2K个以后的一些数与这2K个数的一些交换，将2K个数调整为一对一对的形式。（画个样例想想就明白了）

例子：

1-2-3          树枝： (1->2),(2->1),(2->3),(3->2),(1->2->3),(3->2->1)

代码：（*：生成够2K个数就可以及时退出了，不然TLE）

struct node{
    int u,v,len;
}edge[2000100];

vector<int> graph[100100];

int T,n,k;

int main(){
    cin>>T;
    while(T--){
        scanf("%d%d",&n,&k);
        int c=0;
        rep(i,1,n) graph[i].clear();
        rep(i,1,n-1){
            int x,y;
            scanf("%d%d",&x,&y);
            graph[x].push_back(y);
            graph[y].push_back(x);
            edge[++c].u=x, edge[c].v=y, edge[c].len=1;
            edge[++c].v=x, edge[c].u=y, edge[c].len=1;
        }
        int p=0;
        while(p<=c){
            if(c>=2*k) break;
            ++p;
            int U=edge[p].u, V=edge[p].v;
            int L=graph[U].size();
            rep(i,0,L-1) if(graph[U][i]!=V && c<2*k){
                ++c;
                edge[c].u=graph[U][i];
                edge[c].v=U;
                edge[c].len=edge[p].len+1;
            }
        }
        ll ans=0;
        int ts=min(c,2*k);
        rep(i,1,ts) ans+=(ll)edge[i].len;
        printf("%I64d
",ans/2);
    }
}