fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define fi first
  3. #define se second
  4. #define all(v) v.begin() , v.end()
  5. #define sz(v) int(v.size())
  6. #define unq(v) sort(all(v)); v.resize(unique(all(v)) - v.begin());
  7. using namespace std;
  8.  
  9. typedef long long ll;
  10. typedef pair<int , int> ii;
  11. typedef pair<long long , int> lli;
  12.  
  13. const int maxN = 307;
  14. const int mod = 998244353;
  15.  
  16. int add(int x , int y){
  17.     x += y;
  18.     if (x >= mod) x -= mod;
  19.     return x;
  20. }
  21.  
  22. void self_add(int &x , int y){
  23.     x = add(x , y);
  24. }
  25.  
  26. int sub(int x , int y){
  27.     x -= y;
  28.     if (x < 0) x += mod;
  29.     return x;
  30. }
  31.  
  32. void self_sub(int &x , int y){
  33.     x = sub(x , y);
  34. }
  35.  
  36. int n , m;
  37. vector<ii> E;
  38. vector<int> adj[maxN * maxN];
  39. int dp[maxN * maxN][maxN] , pre[maxN][maxN];
  40.  
  41. struct node{
  42.     int n , p[maxN] , h[maxN];
  43.     vector<int> g[maxN];
  44.  
  45.     void add_edge(int u , int v , int t){
  46.         g[u].push_back(t);
  47.         g[v].push_back(t);
  48.     }
  49.  
  50.     void dfs(int u , int par){
  51.         for (int id : g[u]){
  52.             int v = u ^ (E[id].fi ^ E[id].se);
  53.             if (v != par){
  54.                 h[v] = h[u] + 1;
  55.                 p[v] = id;
  56.                 dfs(v , u);
  57.             }
  58.         }
  59.     }
  60.  
  61.     void match(int x , int u , int v){
  62.         for (int i = 0 ; i < m - 1 ; i++){
  63.             self_add(pre[u][i] , dp[x][i]);
  64.             self_add(pre[v][i] , dp[x][i]);
  65.         }
  66.         while (h[u] > h[v]){
  67.             adj[p[u]].push_back(x);
  68.             u ^= (E[p[u]].fi ^ E[p[u]].se);
  69.         }
  70.         while (h[v] > h[u]){
  71.             adj[p[v]].push_back(x);
  72.             v ^= (E[p[v]].fi ^ E[p[v]].se);
  73.         }
  74.         while (u != v){
  75.             adj[p[u]].push_back(x);
  76.             adj[p[v]].push_back(x);
  77.             u ^= (E[p[u]].fi ^ E[p[u]].se);
  78.             v ^= (E[p[v]].fi ^ E[p[v]].se);
  79.         }
  80.         for (int i = 0 ; i < m - 1 ; i++){
  81.             self_sub(pre[u][i] , dp[x][i]);
  82.             self_sub(pre[v][i] , dp[x][i]);
  83.         }
  84.     }
  85.  
  86.     void build(int u , int par){
  87.         for (int id : g[u]){
  88.             int v = u ^ (E[id].fi ^ E[id].se);
  89.             if (v != par){
  90.                 build(v , u);
  91.                 for (int i = 0 ; i < m - 1 ; i++){
  92.                     self_add(pre[u][i] , pre[v][i]);
  93.                     self_add(dp[p[v]][i] , pre[v][i]);
  94.                 }
  95.             }
  96.         }
  97.     }
  98. } tree[maxN];
  99.  
  100. void solve(){
  101.     cin >> n >> m;
  102.     for (int i = 0 ; i < n ; i++){
  103.         tree[i].n = m;
  104.         for (int j = 1 ; j < m ; j++){
  105.             int u , v;
  106.             cin >> u >> v;
  107.             tree[i].add_edge(u , v , sz(E));
  108.             E.push_back({u , v});
  109.         }
  110.         tree[i].dfs(1 , 0);
  111.         for (int u = 1 ; u <= n ; u++){
  112.             for (int t = 0 ; t < m - 1 ; t++) pre[u][t] = 0;
  113.         }
  114.     }
  115.     for (int i = 0 ; i < m - 1 ; i++) dp[i][i] = 1;
  116.     for (int i = 0 ; i < n ; i++){
  117.         for (int j = i * (m - 1) ; j < (i + 1) * (m - 1) ; j++){
  118.             tree[(i + 1) % n].match(j , E[j].fi , E[j].se);
  119.         }
  120.         tree[(i + 1) % n].build(1 , 0);
  121.     }
  122.     int ans = 0;
  123.     for (int i = (n - 1) * (m - 1) ; i < n * (m - 1) ; i++){
  124.         for (int t = 0 ; t < m - 1 ; t++){
  125.             bool ok = 0;
  126.             for (int j : adj[t]){
  127.                 if (i == j) ok = 1;
  128.             }
  129.             if (ok){
  130.                 self_add(ans , dp[i][t]);
  131.             }
  132.         }
  133.     }
  134.     cout << ans << "\n";
  135. }
  136.  
  137. #define name "A"
  138.  
  139. int main(){
  140.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  141.     if (fopen(name".INP" , "r")){
  142.         freopen(name".INP" , "r" , stdin);
  143.         freopen(name".OUT" , "w" , stdout);
  144.     }
  145.     int t = 1; //cin >> t;
  146.     while (t--) solve();
  147.     return 0;
  148. }
  149.  
  150.  
  151.  
Success #stdin #stdout 0.01s 9644KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Gh3zFp
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!