题目链接
题意
n个点,任意两点之间有一条无向边,每条边的权值都是y,现在给你一个生成树,这个生成树上的权值从y改成了x。问你现在遍历所有的点一次且仅一次的代价和最小是多少?
\((2\leq n \leq 200 000, 1\leq x,y \leq 10^9)\)
思路
- 不是很懂,好像在找规律
- 如果y<x: 那么选在生成树上的边越少越好。
- 一般情况下,可以选到个完全没有用生成树上的边的路径,\(y*(n-1)\);
- 极端情况,有一个点连着剩下n-1个点,即有一个点的度数为n-1,那么一定要选到一条在生成树上的边,\(x+y*(n-2)\)。
- 如果x<=y:那么选的边在生成树上越多越好。
- 我一开始以为是求树的直径,然后并不是 ex:1->2,3->2,2->4,4->5,4->6
- 每个点只经过一次:度数最多为2.
- a->b这条边能不能选:看b有没有把两个度数用掉。所以用dfs。
代码
#include<bits/stdc++.h>
#define DEBUG1
using namespace std;
typedef long long ll;
const int MAXN=200005;
struct Edge{
int to,next;
}edge[MAXN<<1];
int head[MAXN],deg[MAXN];
int cnt,len;
ll ans,n,x,y;
void add_edge(int u,int v){
edge[++cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt;
edge[++cnt].to=u;
edge[cnt].next=head[v];
head[v]=cnt;
}
int tmp=0;
bool dfs(int u,int fa){
#ifdef DEBUG
tmp++;
if(tmp>=20) return false;
#endif
int tot=2;
for(int i=head[u];i;i=edge[i].next){
int to = edge[i].to;
#ifdef DEBUG
printf("u:%d,fa:%d,to:%d,tot:%d\n",u,fa,to,tot);
#endif
if(to==fa) continue;
//dfs(to,v):如果这个为false则表明子节点已经用掉了2条边了
//tot:如果tot==0,那么说明这个点已经用掉2条边了
// 这两种情况下,这一条边都不能用了
if(dfs(to,u)&&tot){
len++;
tot--;
}
}
return tot;
}
int main()
{
scanf("%lld%lld%lld",&n,&x,&y);
int u,v;
bool flag=false;
for(ll i=1;i<n;i++){
scanf("%d%d",&u,&v);
add_edge(u,v);
deg[u]++;
deg[v]++;
if(deg[u]==n-1||deg[v]==n-1)flag=true;
}
if(x>=y){
if(flag) printf("%lld\n",y*(n-2)+x);
else printf("%lld\n",y*(n-1));
return 0;
}
else{
dfs(1,0);
ans=len*x+(n-1-len)*y;
printf("%lld\n",ans);
}
return 0;
}