Forest Program (DFS Method — Ring on Tree)

The meaning of the title:

Every connected block in the desert is a cactus; a connected block is a cactus if and only if there are no heavy edges and self-rings in the connected block , And each side is only covered by at most one simple ring.

After some evaluation, country Z decided to finally turn the desert into a forest by deleting some edges in the desert. Here we define the forest to satisfy: every connected block in the forest is a tree, and the tree is a connected block with the number of edges equal to the number of points minus one. Now given one contains < span id="MathJax-Span-2" class="mrow">n A spot of desert , Please find out how many desert transformation plans meet the requirements in country Z. The two schemes are different if and only if the deleted edge sets in the scheme are different. Since the answer may be very large, please correct the final answer 998244353 span> Output after taking the modulus.

Thinking:

Direct dfs.

 1 #define  IOS ios_base::sync_with_stdio(0); cin.tie(0);

 2 #include //sprintf islower isupper

 3 #include //malloc exit strcat itoa system("cls")

 4 #include //pair

 5 #include //freopen("C:\Users\13606\Desktop\draft.txt","r",stdin);

 6 #include 

 7 //#include  8 //#include

 9 #include 

 10 #include 

 11 #include <set>

 12 #include <string.h>//strstr substr

 13 #include <string>

 14 #include //srand(((unsigned)time(NULL))); Seed n=rand()%10-0~9;

 15 #include 

 16 #include 

 17 #include //priority_queue, greater> q;//less

 18 #include //emplace_back

 19 //#include 

 20 //#include //reverse(a, a+len);// ~! ~! floor

 21 #include //sort + unique: sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)

 22 using  namespace std;//next_permutation(a+1,a+1+n); //prev_permutation

 23 //******************

 24 int abss(int a);

 25 int lowbit(int n);

 26 int Del_bit_1(int n);

 27 int maxx(int a,int b);

 28 int minn(int a,int b);

 29 double fabss(double a);

 30 void swapp(int &a,int &b);

 31 clock_t __STRAT,__END;

 32 double __TOTALTIME;

 33 void _MS(){__STRAT=clock();}

 34 void _ME(){__END=clock( );__TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}

 35 //***********************

 36 #define rint register int

 37 #define fo(a,b,c) for(rint a=b;a<=c;++a)

 38 #define fr(a,b,c) for(rint a=b;a>=c;--a)

 39 #define mem(a,b) memset(a,b ,sizeof(a))

 40 #define pr printf

 41 #define sc scanf

 42 #define ls rt<<1

 43 #define rs rt<<1|1

 44 typedef long long ll;

 45 const double E=2.718281828;

 46 const double PI=acos(-1.0);

 47 //const ll INF=(1LL<<60);

 48 const  int inf=(1<<30);

 49 const double ESP=1e-9;

 50 const int mod=(int)998244353;

 51 const int N=(int)5e5+10;

 52 int read(){

 53 int x=0,f=1;char ch =getchar();

 54 for(;!isdigit(ch); ch=getchar())if(ch=='-')f=-1< span style="color: #000000;">;

 55 for(;isdigit(ch);ch =getchar())x=x*10+ch-'0';

 56 return x*f;

 57 }

 58 ll qpow(ll a,ll b,ll mod)

 59 {

 60  ll ans;

 61 // a%=mod;

 62 ans=1;

 63 while(b!=0)

 64  {

 65 if(b&1)

 66 ans=(ans*a)%mod;

 67 b/=2;

 68 a=(a*a)%mod;

 69 }

 70 return ans;

 71 }

 72

 73 bool vis[N];

 74 ll dep[N];

 75 vectorint> >G(N);

 76

 77 ll loop,other,ans;

 78 void dfs(int u,int v)

 79 {

 80 // cout<

 81 if (vis[v])

 82  {

 83 if(dep[u]<=dep [v])return;

 84 ans*=qpow(2,dep[ u]+1-dep[v],mod)-1;

 85 ans=(ans+mod)%mod;

 86 loop+=dep[u]+1- dep[v];

 87 return;

 88 }

 89 vis[v]=1;

 90 dep[v]=dep[u]+1 span>;

 91 int sz=G[v].size();

 92 for(int i=0;ii)

 93  {

 94 int to=G[v][i];

 95 if(!dep[v]<= dep[to]&&to!=u)

 96  {

 97  dfs(v,to);

 98 }

 99 }

100 }

101

102 int main()

103 {

104 int n,way;

105 while(~sc("%d%d" ,&n,&way))

106  {

107 ans=1;loop=other=< span style="color: #800080;">0;

108 for(int i=1;i<=n;++i )

109 G[i].clear(),dep[i]=vis[i]=0;

110 for(int i=1;i<=way;++i )

111  {

112 int u,v;

113 u=read(),v=read();

114  G[u].push_back(v);

115  G[v].push_back(u);

116 }

117 // bfs({0,1});

118 dfs(0,1);

119 other=way-loop;

120 ans*=qpow(2,other,mod);

121 ans%=mod;

122 // if(loop==0)ans=0;

123 pr("%lld
",ans);

124 //cout<

125 }

126 return 0;

127 }

128

129 /************************************************** ************************************/

130

131 int maxx(int a,int b)

132 {

133 return a>b?a:b;

134 }

135

136 void swapp(int &a,int &b)

137 {

138 a^=b^=a^=b;

139 }

140

141 int lowbit(int n)

142 {

143 return n&(-n);

144 }

145

146 int Del_bit_1(int n)

147 {

148 return n&(n-1);

149 }

150

151 int abss(int a)

152 {

153 return a>0?a:-a;

154 }

155

156 double fabss(double a)

157 {

158 return a>0?a:-a;

159 }

160

161 int minn(int a,int b)

162 {

163 return aa:b;

164 }

 1 #define IOS ios_base::sync_with_stdio(0); cin.tie(0);

 2 #include //sprintf islower isupper

 3 #include //malloc exit strcat itoa system("cls")

 4 #include //pair

 5 #include //freopen("C:\Users\13606\Desktop\draft.txt","r",stdin);

 6 #include 

 7 //#include  8 //#include

 9 #include 

 10 #include 

 11 #include <set>

 12 #include <string.h>//strstr substr

 13 #include <string>

 14 #include //srand(((unsigned)time(NULL))); Seed n=rand()%10-0~9;

 15 #include 

 16 #include 

 17 #include //priority_queue, greater> q;//less

 18 #include //emplace_back

 19 //#include 

 20 //#include //reverse(a, a+len);// ~! ~! floor

 21 #include //sort + unique: sz=unique(b+1,b+n+1)-(b+1);+nth_element(first, nth, last, compare)

 22 using  namespace std;//next_permutation(a+1,a+1+n); //prev_permutation

 23 //******************

 24 int abss(int a);

 25 int lowbit(int n);

 26 int Del_bit_1(int n);

 27 int maxx(int a,int b);

 28 int minn(int a,int b);

 29 double fabss(double a);

 30 void swapp(int &a,int &b);

 31 clock_t __STRAT,__END;

 32 double __TOTALTIME;

 33 void _MS(){__STRAT=clock();}

 34 void _ME(){__END=clock( );__TOTALTIME=(double)(__END-__STRAT)/CLOCKS_PER_SEC;cout<<"Time: "<<__TOTALTIME<<" s"<<endl;}

 35 //***********************

 36 #define rint register int

 37 #define fo(a,b,c) for(rint a=b;a<=c;++a)

 38 #define fr(a,b,c) for(rint a=b;a>=c;--a)

 39 #define mem(a,b) memset(a,b,sizeof(a))

 40 #define pr printf

 41 #define sc scanf

 42 #define ls rt<<1

 43 #define rs rt<<1|1

 44 typedef long long ll;

 45 const double E=2.718281828;

 46 const double PI=acos(-1.0);

 47 //const ll INF=(1LL<<60);

 48 const int inf=(1<<30);

 49 const double ESP=1e-9;

 50 const int mod=(int)998244353;

 51 const int N=(int)5e5+10;

 52 int read(){

 53     int x=0,f=1;char ch=getchar();

 54     for(;!isdigit(ch);ch=getchar())if(ch==‘-‘)f=-1;

 55     for(;isdigit(ch);ch=getchar())x=x*10+ch-‘0‘;

 56     return x*f;

 57 }

 58 ll qpow(ll a,ll b,ll mod)

 59 {

 60     ll ans;

 61 //    a%=mod;

 62     ans=1;

 63     while(b!=0)

 64     {

 65         if(b&1)

 66             ans=(ans*a)%mod;

 67         b/=2;

 68         a=(a*a)%mod;

 69     }

 70     return ans;

 71 }

 72 

 73 bool vis[N];

 74 ll dep[N];

 75 vectorint> >G(N);

 76 

 77 ll loop,other,ans;

 78 void dfs(int u,int v)

 79 {

 80 //    cout<

 81     if(vis[v])

 82     {

 83         if(dep[u]<=dep[v])return;

 84         ans*=qpow(2,dep[u]+1-dep[v],mod)-1;

 85         ans=(ans+mod)%mod;

 86         loop+=dep[u]+1-dep[v];

 87         return;

 88     }

 89     vis[v]=1;

 90     dep[v]=dep[u]+1;

 91     int sz=G[v].size();

 92     for(int i=0;ii)

 93     {

 94         int to=G[v][i];

 95         if(!dep[v]<=dep[to]&&to!=u)

 96         {

 97             dfs(v,to);

 98         }

 99     }

100 }

101 

102 int main()

103 {

104     int n,way;

105     while(~sc("%d%d",&n,&way))

106     {

107         ans=1;loop=other=0;

108         for(int i=1;i<=n;++i)

109             G[i].clear(),dep[i]=vis[i]=0;

110         for(int i=1;i<=way;++i)

111         {

112             int u,v;

113             u=read(),v=read();

114             G[u].push_back(v);

115             G[v].push_back(u);

116         }

117         //    bfs({0,1});

118         dfs(0,1);

119         other=way-loop;

120         ans*=qpow(2,other,mod);

121         ans%=mod;

122         //    if(loop==0)ans=0;

123         pr("%lld
",ans);

124         //cout<

125     }

126     return 0;

127 }

128 

129 /**************************************************************************************/

130 

131 int maxx(int a,int b)

132 {

133     return a>b?a:b;

134 }

135 

136 void swapp(int &a,int &b)

137 {

138     a^=b^=a^=b;

139 }

140 

141 int lowbit(int n)

142 {

143     return n&(-n);

144 }

145 

146 int Del_bit_1(int n)

147 {

148     return n&(n-1);

149 }

150 

151 int abss(int a)

152 {

153     return a>0?a:-a;

154 }

155 

156 double fabss(double a)

157 {

158     return a>0?a:-a;

159 }

160 

161 int minn(int a,int b)

162 {

163     return aa:b;

164 }