Description

有一個(gè)擁有n個(gè)城市的國(guó)家。這個(gè)國(guó)家由n-1條邊連接起來。有一天國(guó)家發(fā)生叛亂。叛軍已占領(lǐng)了一些城市。如果叛軍占領(lǐng)的城市中，存在兩個(gè)城市之間有邊直接相連，則稱這種情況是壞的?，F(xiàn)在并不知道叛軍占領(lǐng)了那些城市，問有多少種情況是壞的？

Input

第1行一個(gè)正整數(shù)n，表示國(guó)家的大小

第2行到第n行，每行兩個(gè)數(shù)字x, y，表示x，y之間有一條邊。

Output

一個(gè)整數(shù)表示方案數(shù)，答案對(duì)(1e9+7)取模

Sample Input

2

1 2

Sample Output

1

HINT

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

?

以下題解搬運(yùn)自出題人yyl：“直接做dp應(yīng)該也是可以的。但是補(bǔ)集轉(zhuǎn)化之后，我們發(fā)現(xiàn)其實(shí)就是問從點(diǎn)集V中選出若干個(gè)點(diǎn)構(gòu)成點(diǎn)集S，滿足S是一個(gè)獨(dú)立集（即S中任意兩點(diǎn)沒有邊直接相連）。設(shè)方案數(shù)為x。答案就是2^n -x?！?/span>

補(bǔ)充：最后輸出2^n -x時(shí)因?yàn)樯婕叭∧?#xff0c;要注意處理負(fù)數(shù)的情況。

?

1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define ll long long 5 using namespace std; 6 const int N=1e5+5; 7 const int mod=1e9+7; 8 int n,x,y,cnt,head[N]; 9 struct edge{int to,next;}e[N*2]; 10 ll ansn=1,dp[N][2]; 11 int read() 12 { 13 int x=0,f=1;char c=getchar(); 14 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 15 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 16 return x*f; 17 } 18 void ins(int u,int v){cnt++;e[cnt].to=v;e[cnt].next=head[u];head[u]=cnt;} 19 void solve(int x,int fa) 20 { 21 dp[x][1]=dp[x][0]=1; 22 for(int i=head[x];i;i=e[i].next) 23 { 24 int to=e[i].to; 25 if(to==fa)continue; 26 solve(to,x); 27 dp[x][0]=(dp[to][0]+dp[to][1])%mod*dp[x][0]%mod; 28 dp[x][1]=dp[to][0]*dp[x][1]%mod; 29 } 30 } 31 int main() 32 { 33 n=read(); 34 for(int i=1;i<n;i++) 35 { 36 x=read();y=read(); 37 ins(x,y);ins(y,x); 38 } 39 solve(1,0); 40 for(int i=1;i<=n;i++)ansn=(ansn*2)%mod; 41 printf("%lld",((ansn-dp[1][0]-dp[1][1])%mod+mod)%mod); 42 return 0; 43 } View Code

轉(zhuǎn)載于:https://www.cnblogs.com/zsnuo/p/7169713.html

總結(jié)

以上是生活随笔為你收集整理的【SRM-05 B】无题？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。