【SRM-05 B】无题？

Description

有一个拥有n个城市的国家。这个国家由n-1条边连接起来。有一天国家发生*。叛军已占领了一些城市。如果叛军占领的城市中，存在两个城市之间有边直接相连，则称这种情况是坏的。现在并不知道叛军占领了那些城市，问有多少种情况是坏的？

Input

第1行一个正整数n，表示国家的大小

第2行到第n行，每行两个数字x, y，表示x，y之间有一条边。

Output

一个整数表示方案数，答案对(1e9+7)取模

Sample Input

1 2

Sample Output

HINT

1 <= n <= 1e5，1<=x，y<=n，x≠y

以下题解搬运自出题人yyl：“直接做dp应该也是可以的。但是补集转化之后，我们发现其实就是问从点集V中选出若干个点构成点集S，满足S是一个独立集（即S中任意两点没有边直接相连）。设方案数为x。答案就是2^n -x。”

补充：最后输出2^n -x时因为涉及取模，要注意处理负数的情况。

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #define ll long long

 using namespace std;

 const int N=1e5+;

 const int mod=1e9+;

 int n,x,y,cnt,head[N];

 struct edge{int to,next;}e[N*];

 ll ansn=,dp[N][];

 int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 void ins(int u,int v){cnt++;e[cnt].to=v;e[cnt].next=head[u];head[u]=cnt;}

 void solve(int x,int fa)

 {

     dp[x][]=dp[x][]=;

     for(int i=head[x];i;i=e[i].next)

     {

         int to=e[i].to;

         if(to==fa)continue;

         solve(to,x);

         dp[x][]=(dp[to][]+dp[to][])%mod*dp[x][]%mod;

         dp[x][]=dp[to][]*dp[x][]%mod;

     }

 }

 int main()

 {

     n=read();

     for(int i=;i<n;i++)

     {

         x=read();y=read();

         ins(x,y);ins(y,x);

     }

     solve(,);

     for(int i=;i<=n;i++)ansn=(ansn*)%mod;

     printf("%lld",((ansn-dp[][]-dp[][])%mod+mod)%mod);

     return ;

 }

秒客网