Code : Count Induced Subgraphs

#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

class Tree {
  public:
    int n;
    vector<vector<int>> adj;
    vector<mint> dp;
    // dp[i] is the count of induced connected subgraph such that the highest
    // vertex is node i.
    Tree(int n) {
        this->n = n;
        adj.resize(n);
        dp.resize(n);
    }

    void dfs(int src, int par) {
        // Start with no children.
        dp[src] = 1;
        for (auto child : adj[src]) {
            if (child == par) {
                continue;
            }
            dfs(child, src);
            // Either ignore this children : dp[src]*1 way
            // Or take this children : dp[src]*dp[child] ways
            dp[src] += dp[src] * dp[child];
        }
    }
};

void solve() {
    int n;
    cin >> n;

    Tree t(n);
    int m = n - 1;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        t.adj[x].push_back(y);
        t.adj[y].push_back(x);
    }

    t.dfs(0, -1);
    mint ans = 0;
    for (int i = 0; i < n; i++) {
        ans += t.dp[i];
    }
    cout << ans.val() << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}

#include <atcoder/dsu>
#include <atcoder/modint>
#include <bits/stdc++.h>

using namespace std;
using namespace atcoder;

using mint = modint998244353;

void solve() {
    int n;
    cin >> n;

    vector<pair<int, int>> edges;
    int m = n - 1;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        x--;
        y--;
        edges.push_back({x, y});
    }

    mint ans = 0;

    int full_mask = 1 << n;
    for (int msk = 0; msk < full_mask; msk++) {
        set<int> have;
        for (int i = 0; i < n; i++) {
            if ((1 << i) & msk) {
                have.insert(i);
            }
        }

        dsu d(n);
        for (auto edge : edges) {
            if (have.count(edge.first) && have.count(edge.second)) {
                d.merge(edge.first, edge.second);
            }
        }

        set<int> distinct_leaders;
        for (auto src : have) {
            distinct_leaders.insert(d.leader(src));
        }
        if (distinct_leaders.size() == 1) {
            ans += 1;
        }
    }

    cout << ans.val() << endl;
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}