360网站图标怎么做,他达那非片能延时多久,天津塘沽爆炸,天津市网站建设+网页制作Description 有一个拥有n个城市的国家。这个国家由n-1条边连接起来。有一天国家发生叛乱。叛军已占领了一些城市。如果叛军占领的城市中#xff0c;存在两个城市之间有边直接相连#xff0c;则称这种情况是坏的。现在并不知道叛军占领了那些城市#xff0c;问有多少种情况是…Description 有一个拥有n个城市的国家。这个国家由n-1条边连接起来。有一天国家发生叛乱。叛军已占领了一些城市。如果叛军占领的城市中存在两个城市之间有边直接相连则称这种情况是坏的。现在并不知道叛军占领了那些城市问有多少种情况是坏的 Input 第1行一个正整数n表示国家的大小 第2行到第n行每行两个数字x, y表示xy之间有一条边。 Output 一个整数表示方案数答案对(1e97)取模 Sample Input 2 1 2 Sample Output 1 HINT 1 n 1e51xynx≠y 以下题解搬运自出题人yyl“直接做dp应该也是可以的。但是补集转化之后我们发现其实就是问从点集V中选出若干个点构成点集S满足S是一个独立集即S中任意两点没有边直接相连。设方案数为x。答案就是2^n -x。” 补充最后输出2^n -x时因为涉及取模要注意处理负数的情况。 1 #includecstdio2 #includealgorithm3 #includecstring4 #define ll long long5 using namespace std;6 const int N1e55;7 const int mod1e97;8 int n,x,y,cnt,head[N];9 struct edge{int to,next;}e[N*2];
10 ll ansn1,dp[N][2];
11 int read()
12 {
13 int x0,f1;char cgetchar();
14 while(c0||c9){if(c-)f-1;cgetchar();}
15 while(c0c9){xx*10c-0;cgetchar();}
16 return x*f;
17 }
18 void ins(int u,int v){cnt;e[cnt].tov;e[cnt].nexthead[u];head[u]cnt;}
19 void solve(int x,int fa)
20 {
21 dp[x][1]dp[x][0]1;
22 for(int ihead[x];i;ie[i].next)
23 {
24 int toe[i].to;
25 if(tofa)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 nread();
34 for(int i1;in;i)
35 {
36 xread();yread();
37 ins(x,y);ins(y,x);
38 }
39 solve(1,0);
40 for(int i1;in;i)ansn(ansn*2)%mod;
41 printf(%lld,((ansn-dp[1][0]-dp[1][1])%modmod)%mod);
42 return 0;
43 } View Code转载于:https://www.cnblogs.com/zsnuo/p/7169713.html
