Description：

给一棵树，每个点有一个价值，价值只能取一次，有 $k$ 次机会走从一开始的一条链，最大化获得的价值。

$1\leqslant n\leqslant 200000$

Solution：

首先有一个贪心方法，就是每次选择到根节点权值和最大的叶子节点选择，然后把这条路径的点的权值都删掉。发现删掉一个点的点权会影响的是它的子树，于是可以用 $DFS$ 序 $+$ 线段树维护，每次暴力向上跳，把跳过的标记，并在子树里减一下，遇到标记或者跳到根就退出，这样均摊是 $O(n\log n)$ 的，注意加减会算重，所以在子树里加上父节点的值，然后再父节点里再减就没什么问题了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,k;

#define MAXN 200010

typedef long long ll;

struct edge 

{

	int to,nxt;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

ll val[MAXN];

void add(int a,int b)

{

	++edgenum;e[edgenum].to = b;e[edgenum].nxt = lin[a];lin[a] = edgenum;

	++edgenum;e[edgenum].to = a;e[edgenum].nxt = lin[b];lin[b] = edgenum;

	return;

}

int rnk[MAXN],tot = 0,siz[MAXN],th[MAXN];

bool v[MAXN];

int fa[MAXN];

void dfs(int k)

{

	v[k] = true;

	rnk[k] = ++tot;siz[k] = 1;th[tot] = k;

	for(int i = lin[k];i != 0;i = e[i].nxt)

	{

		if(!v[e[i].to])

		{

			fa[e[i].to] = k;

			val[e[i].to] += val[k];

			dfs(e[i].to);

			siz[k] += siz[e[i].to];

		}

	}

	return;

}

struct node

{

	int lc,rc;

	ll maxv,tag;

	int pos;

}t[MAXN << 1];

int ptr = 0;

int newnode(){return ++ptr;}

int root;

#define mid ((l + r) >> 1)

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void set(int rt,int p,ll k,int l,int r)

{

	if(l == r)

	{

		t[rt].maxv = k;

		t[rt].pos = l;

		return;

	}

	if(p <= mid)set(t[rt].lc,p,k,l,mid);

	else set(t[rt].rc,p,k,mid + 1,r);

	if(t[t[rt].lc].maxv > t[t[rt].rc].maxv)

	{

		t[rt].maxv = t[t[rt].lc].maxv;

		t[rt].pos = t[t[rt].lc].pos;

	}

	else

	{

		t[rt].maxv = t[t[rt].rc].maxv;

		t[rt].pos = t[t[rt].rc].pos;

	}

	return;

}

void pushdown(int rt)

{

	if(t[rt].tag != 0)

	{

		t[t[rt].lc].maxv += t[rt].tag;t[t[rt].lc].tag += t[rt].tag;

		t[t[rt].rc].maxv += t[rt].tag;t[t[rt].rc].tag += t[rt].tag;

		t[rt].tag = 0;

	}

	return;

}

void add(int rt,int L,int R,ll k,int l,int r)

{

	if(L <= l && r <= R)

	{

		t[rt].maxv += k;t[rt].tag += k;

		return;

	}

	pushdown(rt);

	if(L <= mid)add(t[rt].lc,L,R,k,l,mid);

	if(R > mid)add(t[rt].rc,L,R,k,mid + 1,r);

	t[rt].maxv = max(t[t[rt].lc].maxv,t[t[rt].rc].maxv);

	if(t[t[rt].lc].maxv > t[t[rt].rc].maxv)

	{

		t[rt].maxv = t[t[rt].lc].maxv;

		t[rt].pos = t[t[rt].lc].pos;

	}

	else

	{

		t[rt].maxv = t[t[rt].rc].maxv;

		t[rt].pos = t[t[rt].rc].pos;

	}

	return;

}

ll query(int rt,int p,int l,int r)

{

	if(l == r)return t[rt].maxv;

	pushdown(rt);

	if(p <= mid)return query(t[rt].lc,p,l,mid);

	else return query(t[rt].rc,p,mid + 1,r);

}

ll calc()

{

	int pos = th[t[root].pos];

	ll res = t[root].maxv;

	for(int i = pos;i != 0 && !v[i];i = fa[i])

	{

		v[i] = true;

		add(root,rnk[i],rnk[i] + siz[i] - 1,-query(root,rnk[i],1,n),1,n);

		if(fa[i] && !v[fa[i]])add(root,rnk[i],rnk[i] + siz[i] - 1,query(root,rnk[fa[i]],1,n),1,n);

	}

	return res;

}

int main()

{

	scanf("%d%d",&n,&k);

	for(int i = 1;i <= n;++i)scanf("%lld",&val[i]);

	int a,b;

	for(int i = 1;i < n;++i)

	{

		scanf("%d%d",&a,&b);

		add(a,b);

	}

	dfs(1);

	build(root,1,n);

	for(int i = 1;i <= n;++i)set(root,rnk[i],val[i],1,n);

	ll ans = 0;

	memset(v,false,sizeof(v));

	for(int i = 1;i <= k;++i)

	{

		ans += calc();

	}

	cout << ans << endl;

	return 0;

}