文档章节

CodeForces - 618D Hamiltonian Spanning Tree

o
 osc_x4h57ch8
发布于 2018/04/24 11:19
字数 835
阅读 0
收藏 0

「深度学习福利」大神带你进阶工程师,立即查看>>>

Discription

A group of n cities is connected by a network of roads. There is an undirected road between every pair of cities, so there are  roads in total. It takes exactly yseconds to traverse any single road.

spanning tree is a set of roads containing exactly n - 1 roads such that it's possible to travel between any two cities using only these roads.

Some spanning tree of the initial network was chosen. For every road in this tree the time one needs to traverse this road was changed from y to x seconds. Note that it's not guaranteed that x is smaller than y.

You would like to travel through all the cities using the shortest path possible. Given nxy and a description of the spanning tree that was chosen, find the cost of the shortest path that starts in any city, ends in any city and visits all cities exactly once.

Input

The first line of the input contains three integers nx and y (2 ≤ n ≤ 200 000, 1 ≤ x, y ≤ 109).

Each of the next n - 1 lines contains a description of a road in the spanning tree. The i-th of these lines contains two integers ui and vi (1 ≤ ui, vi ≤ n) — indices of the cities connected by the i-th road. It is guaranteed that these roads form a spanning tree.

Output

Print a single integer — the minimum number of seconds one needs to spend in order to visit all the cities exactly once.

Examples

Input
5 2 3
1 2
1 3
3 4
5 3
Output
9
Input
5 3 2
1 2
1 3
3 4
5 3
Output
8

Note

In the first sample, roads of the spanning tree have cost 2, while other roads have cost 3. One example of an optimal path is .

In the second sample, we have the same spanning tree, but roads in the spanning tree cost 3, while other roads cost 2. One example of an optimal path is .

 

 

    题目要求就是先给你一个边权都是y的完全图,然后再把一棵树的边都改成x,之后问你图中权值最小的一个包含n个点的链的权值是多少。

    分类讨论一下:

        1.如果y<=x的话,我们尽量保留原图中的边就好了。 可以发现只要给出的树 不是菊花图的话,总能找出一条包含n个点的链,使得链上的边权都是y。所以这种情况特判一下是不是菊花图就好了。

        2.如果x<y的话,我们是希望尽量保留给出的树中的边的,这部分其实就是求树的最小路径覆盖,也就是选出尽量多的边,使得它们构成的联通块在树中都是链,这样用y把链首尾相连就可以了(两个链相接的地方在树中一定没有边,不然答案还能+1,于最优性不符)。  直接一个树上dp就ojbk了。

 

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=200005;
int to[maxn*2],ne[maxn*2],num;
int hd[maxn],n,m,X,Y,D[maxn],A,f[maxn][3];
inline void add(int x,int y){ to[++num]=y,ne[num]=hd[x],hd[x]=num;}

void dfs(int x,int fa){
	for(int i=hd[x];i;i=ne[i]) if(to[i]!=fa){
		dfs(to[i],x);
		f[x][2]=max(f[x][2]+f[to[i]][2],f[x][1]+f[to[i]][1]+1);
		f[x][1]=max(f[x][1]+f[to[i]][2],f[x][0]+f[to[i]][1]+1);
		f[x][0]+=f[to[i]][2];
    }
	
	f[x][1]=max(f[x][1],f[x][0]);
	f[x][2]=max(f[x][2],f[x][1]);
}

int main(){
	int uu,vv;
	scanf("%d%d%d",&n,&X,&Y);
	for(int i=1;i<n;i++) scanf("%d%d",&uu,&vv),add(uu,vv),add(vv,uu),D[uu]++,D[vv]++;
	if(Y<=X){
		for(int i=1;i<=n;i++) if(D[i]==n-1){
			printf("%lld\n",(n-2)*(ll)Y+(ll)X);
			return 0;
		}
		printf("%lld\n",(n-1)*(ll)Y);
		return 0;
	}
	
	dfs(1,-1),A=f[1][2];
	
	printf("%lld\n",X*(ll)A+(n-A-1)*(ll)Y);
	return 0;
}

  

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

大数据研发学习之路--Hadoop集群搭建

阅读编译文档 准备一个hadoop源码包,我选择的hadoop版本是:hadoop-2.7.7-src.tar.gz,在hadoop-2.7.7的源码 包的根目录下有一个文档叫做BUILDING.txt,这其中说明了编译hadoop所需要的一些...

DSJ-shitou
21分钟前
8
0
OSChina 周五乱弹 —— 特么是别的公司派来的特洛伊木马吧?

Osc乱弹歌单(2020)请戳(这里) 【今日歌曲】 小小编辑推荐:《我会守在这里》- 毛不易 《我会守在这里》- 毛不易 手机党少年们想听歌,请使劲儿戳(这里) @FalconChen :股市连跪了五天,...

小小编辑
22分钟前
26
2
如何在find中排除目录。命令 - How to exclude a directory in find . command

问题: I'm trying to run a find command for all JavaScript files, but how do I exclude a specific directory? 我正在尝试为所有JavaScript文件运行find命令,但是如何排除特定目录? ......

法国红酒甜
今天
69
0
《Java8实战》笔记(02):通过行为参数传递代码

本文源码 应对不断变化的需求 通过筛选苹果阐述通过行为参数传递代码 初试牛刀:筛选绿苹果 public static List<Apple> filterGreenApples(List<Apple> inventory){List<Apple> result = ......

巨輪
今天
19
0
JeeSite 4 架构特点、安全方面、为什么好、工匠精神、不忘初心

1、底层架构 以 Spring Boot 2 为基础,Maven 多项目依赖,模块分项目,松耦合,方便模块升级、增减模块。 模块化的数据库自动升级程序,当模块升级代码需要更新数据库时,自动执行对应版本 ...

ThinkGem
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部