首页 > 代码库 > 汕头市队赛 yyl杯1 T2

汕头市队赛 yyl杯1 T2

B SRM 05 - YYL 杯 R1

背景&&描述

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

输入格式

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

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

输出格式

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

样例输入

2

1 2

样例输出

1

数据范围与约定

  • 对于0%的数据,和样例一毛一样。
  • 对于前20%的数据,技术分享
  • 对于接下来10%的数据,保证给出的是一条链,且 1 <= n <= 1e5
  • 对于接下来20%的数据,保证只有一个点的度数技术分享,其他点度数技术分享,且 1 <= n <= 1e5
  • 对于接下来20%的数据,保证给出的是一棵满二叉树,且 1 <= n <= 1e5
  • 对于剩下的数据,1 <= n <= 1e5,技术分享

样例解释

只有1和2同时叛变时才满足题意。

这道题往补集上考虑会容易很多 所有的情况当然一共有2^n种 我们只要算出从点集V中选出若干个点构成点集S,满足S是一个独立集(即S中任意两点没有边直接相连)中S的数量x

答案就是2^n-x了 果然转换很重要

 

技术分享
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int M=1e5+7,mod=1e9+7;
int read(){
    int ans=0,f=1,c=getchar();
    while(c<0||c>9){if(c==-) f=-1; c=getchar();}
    while(c>=0&&c<=9){ans=ans*10+(c-0); c=getchar();}
    return ans*f;
}
int n,first[M],cnt;
LL f[M][2],ans=1;
struct node{int to,next;}e[2*M];
void ins(int a,int b){cnt++; e[cnt].to=b; e[cnt].next=first[a]; first[a]=cnt;}
void insert(int a,int b){ins(a,b); ins(b,a);}
void dp(int x,int last){
    f[x][0]=f[x][1]=1;
    for(int i=first[x];i;i=e[i].next){
        int now=e[i].to;
        if(now==last) continue;
        dp(now,x);
        f[x][0]=(f[now][0]+f[now][1])%mod*f[x][0]%mod;
        f[x][1]=f[now][0]*f[x][1]%mod;
    }
}
int main()
{
    int x,y;
    n=read();
    for(int i=1;i<n;i++) x=read(),y=read(),insert(x,y);
    dp(1,0);
    for(int i=1;i<=n;i++) ans=ans*2%mod; 
    printf("%lld\n",((ans-f[1][0]-f[1][1])%mod+mod)%mod);
    return 0;
}
View Code

 

汕头市队赛 yyl杯1 T2