1 #include<iostream> 2 #include<vector> 3 #include<algorithm> 4 #define mod 10081 5 using namespace std; 6 vector <int> e[100010]; 7 int flag[100010]; 8 int f[100010][2]; 9 void dfs(int x) 10 { 11 for(int i=0;i<e[x].size();i++) 12 { 13 if (!flag[e[x][i]]) 14 { 15 flag[e[x][i]]=1; 16 dfs(e[x][i]); 17 f[x][1]=(long long)(f[x][1]*f[e[x][i]][0])%mod; 18 f[x][0]=(f[e[x][i]][0]+f[e[x][i]][1])%mod*f[x][0]%mod; 19 } 20 } 21 } 22 int main () 23 { 24 int n; 25 cin>>n; 26 for (int i=1,x,y;i<=n-1;i++) 27 { 28 cin>>x>>y; 29 e[x].push_back(y); 30 e[y].push_back(x); 31 } 32 for (int i=1;i<=n;i++) sort(e[i].begin(),e[i].end()); 33 for (int i=1;i<=n;i++) f[i][0]=f[i][1]=1; 34 flag[1]=1; 35 dfs(1); 36 cout<<(f[1][0]+f[1][1])%mod; 37 }
JZOJ 3034. 【NOIP2012模拟10.17】独立集
原文:https://www.cnblogs.com/zjzjzj/p/11140818.html