Bubble Cup X - Finals E - Casinos and travel

题意:一棵树,一个人刚开始心情很好,每走过一个带标记的点心情就不好了,走完一个城市他随机选一个相邻的另外一个城市走,问有多少种方式选择起点并指定哪些点打标记,使得这个人无路可走的时候心情是好的。

考虑每个结点,因为从这个点出发的所有路线均是到达叶子节点的(并且唯一),所以要使整条链黑色的点个数为偶数。假定先指定整棵树除起点和叶子节点以外的颜色,发现对于一条道路的答案,无论道路上有多少黑色顶点,改变叶子结点的颜色都能使得黑色点数量达到要求的奇偶性。所以考虑以每个点为根(起点),那么它的方案数一定是所有除叶子以外指派的方法数(当根为一个叶子时,从叶子中去除这个点)。

$Ans=\sum_{i=1}^{N} 2^{N-(leaf-[i~is~a~leaf])}$

其中$leaf$是叶子数

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
#include <bits/stdc++.h>
using namespace std;
const int maxn=100000+5;
vector<int > g[maxn];
int deg[maxn],fac[maxn];
int n;
const int mo=1000000000+7;
void pre()
{
fac[0]=1;
for(int i=1;i<maxn;i++) fac[i]=(fac[i-1]<<1)%mo;
}
int main()
{
pre();
scanf("%d",&n);
for(int i=0;i<n-1;i++){
int from,to;
scanf("%d%d",&from,&to);
deg[from]++;deg[to]++;
}
int Ans=0,lef=0;
for(int i=1;i<=n;i++){
if(deg[i]==1) lef++;
}
for(int i=1;i<=n;i++){
Ans=(Ans+fac[n-(lef-(deg[i]==1))])%mo;
}
printf("%d\n",Ans);
return 0;
}