Submission #1003160

#	Time	Username	Problem	Language	Result	Execution time	Memory
1003160		vjudge1	Subtree (INOI20_subtree)	C++17	20 / 100	778 ms	1048576 KiB

Main

#include <bits/stdc++.h>
using namespace std;
int n, m;
namespace SUBT1 {
  const int N = 1e5+10;
  vector<int> g[N];
  struct DSU {
    vector<int> e;
    DSU(int n) {
      e=vector<int>(n+1, -1);
    }
    int get(int x) {
      if(e[x] < 0)return x;
      return e[x] = get(e[x]);
    }
    int sz(int x) {
      return -e[get(x)];
    }
    bool unite(int a, int b) {
      a=get(a),b=get(b);
      if(a == b)return false;
      if(-e[a] > -e[b]) {
        swap(a,b);
      }
      e[b]+=e[a];
      e[a] = b;
      return true;
    }
  };
  void solve() {
    cin >> m;
    for(int i  = 0;i<m;i++) {
      int u, v;
      cin >> u >> v;
      u--,v--;
      g[u].push_back(v);
    }
    int ans=0;
    for(int mask = 1;mask<(1<<n);mask++) {
      DSU d(n);
      int cnt=0;
      int f=-1, sz=0;
      for(int j = 0;j<n;j++) {
        if(mask&(1<<j)) {
          sz++;
          f=j;
          for(int to:g[j]){
            if(mask&(1<<to)) {
              d.unite(to, j);
              cnt++;
            }
          }
        }
      }
      if(d.sz(f) == sz and cnt==sz-1){
        ans++;
      }
    }
    cout << ans <<"\n";
  }
}
namespace SUBT2 {
  const int N = 1e5+10;
  const long long mod = 1e9+7;
  long long dp[N];
  long long ans=0;
  vector<int> g[N];
  void dfs(int at, int p) {
    dp[at]=1;
    long long res=1;
    for(int to:g[at]) {
      if(to==p)continue;
      dfs(to,at);
      res*=dp[to];
      res%=mod;
    }
    dp[at]=res;
    ans+=dp[at];
    dp[at]++;
    ans%=mod;
  }
  void solve() {
    cin >> m;
    for(int i = 0;i<m;i++) {
      int u, v;
      cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
    }
    dfs(1, 0);
    cout << ans << "\n";
  }
};
int main () {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  if(n <= 20) {
    SUBT1::solve();
  }
  else {
    SUBT2::solve();
  }
}

• Subtask 1: 8 / 8
• Subtask 2: 12 / 12
• Subtask 3: 0 / 30
• Subtask 4: 0 / 50