Codeforce 1213G Path query 并查集

You are given a weighted tree consisting of nn vertices. Recall that a tree is a connected graph without cycles. Vertices uiui and vivi are connected by an edge with weight wiwi.

You are given mm queries. The ii-th query is given as an integer qiqi. In this query you need to calculate the number of pairs of vertices (u,v)(u,v) (u<vu<v) such that the maximum weight of an edge on a simple path between uu and vv doesn't exceed qiqi.

Input

The first line of the input contains two integers nn and mm (1≤n,m≤2⋅1051≤n,m≤2⋅105) — the number of vertices in the tree and the number of queries.

Each of the next n−1n−1 lines describes an edge of the tree. Edge ii is denoted by three integers uiui, vivi and wiwi — the labels of vertices it connects (1≤ui,vi≤n1≤ui,vi≤n, ui≠viui≠vi) and the weight of the edge (1≤wi≤2⋅1051≤wi≤2⋅105). It is guaranteed that the given edges form a tree.

The last line of the input contains mm integers q1,q2,…,qmq1,q2,…,qm (1≤qi≤2⋅1051≤qi≤2⋅105), where qiqi is the maximum weight of an edge in the ii-th query.

Output

Print mm integers — the answers to the queries. The ii-th value should be equal to the number of pairs of vertices (u,v)(u,v) (u<vu<v) such that the maximum weight of an edge on a simple path between uu and vv doesn't exceed qiqi.

Queries are numbered from 11 to mm in the order of the input.

Examples

Input

Output

21 7 15 21 3

Input

1 2
1 2

Output

0 0

Input

Output

1 3 3

Note

The picture shows the tree from the first example:

题目大意:给你一颗带权树,每次询问一个qi,问有多少条路径满足该路径上的最大值小于等于qi

题目思路:

我们只需要考虑,路径不超过i的边有多少条

我们从小到大将边权排序,一次一次的往图中加边,我们考虑当新加的一条边时,这条边会连接两个联通块,这时会增加一部分贡献,这部分贡献就是sum[a]*sum[b](sum数组表示当前联通块的大小,也就是节点数的多少).之后考虑两个情况:

第一种当前加的边权值相同:

首先理解：毎向一个联通块b添加一个点a，路径条数就会增加 sum[a]*sum[b]

假设当前图无边,加进1 2 1 ,所以权值 0+=1*1 //以下这所有算式表示sum[a]*sum[b] 然后更新让2->1 sum[1]+=sum[2] sum[2]=0,sum[1]为根

再来一条边 2 3 1 此时 2为1 1+=2*1=3 然后更新 3->2->1 sum[1]继续更新

以上为第一种情况

第二种当不同时,因为没有考虑到权值全为1的连通块中的数目,所以我们要加上为1的：

此时边权为1的边完了，那么为1的联通块中数目就是3，再来一条边 3 4 2 此时 sum[3]=3 所以合并之后 0+=3*1=3

边权为2的是1(但这是混合图)，所以要加上为1的联通块内部的路径数PS：(这一部分就是前缀和),仔细体会一下

AC：

#include <bits/stdc++.h>
/*#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>*/
#pragma GCC optimize(2)
typedef long long ll;
typedef unsigned long long ull;
const int mod=1000;
const int maxn=1e6+5;
const ll INF=10000000000000005;
using namespace std;
ll n,m,p;
ll pre[maxn];
ll sum[maxn];
struct node{
    int s,e;ll w;
    bool friend operator<(node a,node b)
    {
        return a.w<b.w;
    }
}edge[maxn];
struct Save{
    ll  w;int id;
    bool friend operator<(Save a,Save b)
    {
        return a.w<b.w;
    }
}save[maxn];
ll res[maxn];
int Find(int x)
{
    return pre[x]==x?x:pre[x]=Find(pre[x]);
}
int main()
{
    ll maxl=-1;
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n-1;i++) scanf("%lld%lld%lld",&edge[i].s,&edge[i].e,&edge[i].w);
    for(int i=1;i<=m;i++){
        scanf("%d",&save[i].w);
        save[i].id=i;
        maxl=max(maxl,save[i].w);
    }
    sort(edge+1,edge+n);
    sort(save+1,save+1+m);
    for(int i=1;i<=n;i++) pre[i]=i,sum[i]=1;
    for(int i=1;i<=n-1;i++)
    {
        int dx=Find(edge[i].s),dy=Find(edge[i].e);
        if(dx!=dy)
        {
            //printf("dx:%d  dy:%d  sumx:%d  sumy:%d   w:%d\n",dx,dy,sum[dx],sum[dy],edge[i].w);
            ll temp=sum[dx]*sum[dy];
            sum[dx]+=sum[dy];sum[dy]=0;
            pre[dy]=dx;
            res[edge[i].w]+=temp;
        }
    }
    int s=1;
    ll sum=0;
    for(int i=1;i<=maxl;i++)
        res[i]=res[i-1]+res[i];
    for(int i=1;i<=m;i++)
    {
        while(s<save[i].w) s++;
        pre[save[i].id]=res[s];
    }
    for(int i=1;i<=m;i++)
        printf("%lld ",pre[i]);
}
/***
样例测试空间:
6
5
1 2
2 3
3 1
3 5
2 6
***/

总结：

这次一定要记住这个思想了，询问路径数时，可以一个点一个点的往里加，每次添加一个点，路径数就是+联通块内点的个数；