牛客网NOIP赛前集训营 提高组 第5场 T2 旅游-LMLPHP

【题解】

  我们可以发现不在最小生成树上的边一定不能多次经过,因为一条不在最小生成树上的边(u,v)的边权比最小生成树上(u,v)之间的路径更长,选择不在最小生成树上的边一定不划算。

  我们还需要确定最小生成树上哪些边需要经过两次。我们发现如果某个点当前的度为奇数,这个点到它的父亲的边要经过两次,所以我们在它和它父亲之间多连上一条边(即把他们的度都加1).

  这样一次dfs我们就可以从下往上确定出需要经过两次的边。

 #include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
#define N 500010
#define rg register
using namespace std;
const int Mod=;
int n,m,tot,cnt,last[N],in[N],fa[N];
LL ans,Pow[N];
struct edge{int to,pre,dis;}e[N<<];
struct rec{int u,v;}r[N];
inline int read(){
int k=,f=; char c=getchar();
while(c<''||c>'')c=='-'&&(f=-),c=getchar();
while(''<=c&&c<='')k=k*+c-'',c=getchar();
return k*f;
}
void dfs(int x,int f,int eg){
for(rg int i=last[x],to;i;i=e[i].pre)if((to=e[i].to)!=f) dfs(to,x,i);
if((in[x]&)&&x!=) ans=(ans+Pow[e[eg].dis])%Mod,in[f]++;
}
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main(){
n=read(); m=read(); Pow[]=;
for(rg int i=;i<=m;i++){
Pow[i]=(Pow[i-]<<)%Mod; ans=(ans+Pow[i])%Mod;
in[r[i].u=read()]++; in[r[i].v=read()]++;
}
for(rg int i=;i<=n;i++) fa[i]=i;
for(rg int i=;i<=m;i++){
int u=r[i].u,v=r[i].v;
if(find(u)!=find(v)){
e[++tot]=(edge){u,last[v],i}; last[v]=tot;
e[++tot]=(edge){v,last[u],i}; last[u]=tot;
fa[find(u)]=find(v);
cnt++; if(cnt==n-) break;
}
}
dfs(,,);
printf("%lld\n",ans);
return ;
}
05-21 11:18