C. Linova and Kingdom

There are n cities and n−1 two-way roads connecting pairs of cities in the kingdom. From any city, you can reach any other city by walking through some roads. The cities are numbered from 1 to n, and the city 1 is the capital of the kingdom. So, the kingdom has a tree structure.

As the queen, Linova plans to choose exactly k cities developing industry, while the other cities will develop tourism. The capital also can be either industrial or tourism city.

A meeting is held in the capital once a year. To attend the meeting, each industry city sends an envoy. All envoys will follow the shortest path from the departure city to the capital (which is unique).

Traveling in tourism cities is pleasant. For each envoy, his happiness is equal to the number of tourism cities on his path.

In order to be a queen loved by people, Linova wants to choose k cities which can maximize the sum of happinesses of all envoys. Can you calculate the maximum sum for her?

input

1
2
3
4
5
6
7
7 4
1 2
1 3
1 4
3 5
3 6
4 7

output

1
7

img

考虑例子，猜想优先选最深的节点 ？或首先选叶子节点？首先选叶子节点是有问题，比如

k=3 , 可以看出先选叶子或者最深是不可行的。可以观察到：1. 每选一个分支节点，都会使得其所有子孙节点的收益 - 1。2、选择一个节点 u 的收益为 这点的深度 l[u] - sum[u] , sum[u] 为 u 所有子孙节点个数。

所以按照 l[u] - sum[u] 排序，依次选择即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
const int MAX=200000+10;
int n,k,u,v;
bool vis[MAX],color[MAX];
int l[MAX],fa[MAX];
ll ans=0;
int sum[MAX];
struct edge{
	int to,next;
}e[MAX*2];
int h[MAX],tot=0;
void addedge(int u,int v){
	e[tot].to =v;
	e[tot].next = h[u];
	h[u] = tot++;
}
struct node{
	int i,sum;
	node(int _i,int _sum){
		i=_i;sum=_sum;
	} 
	bool operator < (const node &x)const{
		return l[i] - sum < l[x.i] - x.sum;
	}
};
priority_queue<node>q;
int dfs(int u){
	vis[u]=1;
	int cnt=0;
	for(int i=h[u];i!=-1;i=e[i].next){
		int v = e[i].to;
		if(vis[v]) continue;
		l[v]=l[u]+1;
		fa[v]=u;
		cnt += dfs(v) +1;
	}
	q.push(node(u,cnt));
	sum[u]=cnt;
	return cnt;
}
int main(){
	//freopen("in","r",stdin);
	mem(h,-1);mem(vis,0);mem(color,0);
	sf(n);sf(k);
	fi(i,0,n-1){
		sf(u);sf(v);
		addedge(u,v); addedge(v,u);
	}
	fa[1]=-1;l[1]=0;
	dfs(1);
	while(k && !q.empty()){
		node t = q.top();
		q.pop();
		color[t.i]=1;
		k--;
	}
	fi(i,1,n+1){
		if(color[i])
			ans += l[i] - sum[i];
	}
	printf("%lld\n",ans);
	return 0;
}