Submission #13644686

---

Source Code Expand

#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vi2;
typedef vector<vi2> vi3;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<ll> vll;
typedef vector<vll> vll2;
typedef vector<vll2> vll3;
typedef vector<bool> vb;

#define el '\n'
#define rep(i, a, b) for (int i = a; i < b; i++)
#define repi(i, a, b) for (int i = a; i >= b; i--)
#define umap unordered_map
#define uset unordered_set
#define vec vector
#define loop(a) for (auto &x : a)
#define all(a) a.begin(), a.end()
#define mp make_pair

int n, m;
vec<vec<pii>> adj;
vll edge_mask;
ll ans = 0;

void dfs(int which, ll mask, int in_ex) {
#ifdef LOCAL
    // cout << "which:" << which << " mask:" << mask << " bits:" << __builtin_popcountll(mask) << el;
#endif
    if (which == m) {
        int edge_left = n - 1 - __builtin_popcountll(mask);
#ifdef LOCAL
        assert(edge_left >= 0);
        // cout << "edge_left=" << edge_left << el;
#endif
        ans += (ll)in_ex * (1LL << edge_left);
        return;
    }
    dfs(which + 1, mask, in_ex);
    dfs(which + 1, mask | edge_mask[which], -in_ex);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    adj = vec<vec<pii>>(n);
    rep(i, 0, n - 1) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        adj[a].emplace_back(b, i);
        adj[b].emplace_back(a, i);
    }
    cin >> m;
    edge_mask = vll(m);
    rep(i, 0, m) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        queue<int> q;
        vii from(n, {-1, -1});
        q.push(u);
        from[u] = {u, -1};
        while (!q.empty()) {
            int h = q.front();
            q.pop();
            if (h == v) {
                break;
            }
            loop(adj[h]) {
                if (from[x.first].first == -1) {
                    from[x.first] = {h, x.second};
                    q.push(x.first);
                }
            }
        }
        set<int> edges;
        int work = v;
        while (work != u) {
            edges.insert(from[work].second);
            work = from[work].first;
        }
#ifdef LOCAL
        cout << "edges for " << i << ":";
        loop(edges) {
            cout << x << ' ';
        }
        cout << el;
#endif
        loop(edges) {
            edge_mask[i] += 1LL << x;
        }
#ifdef LOCAL
        cout << "edge_mask for " << i << ":" << edge_mask[i] << el;
#endif
    }
    dfs(0, 0, 1);
    cout << ans << el;
}

Submission Info

Judge Result