首页 > 代码库 > 汕头市队赛 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; }
汕头市队赛 yyl杯1 T2
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。