Submission #9614620

---

Source Code Expand

#include <iostream>
#include <vector>
#define rep(i, n) for(i = 0; i < n; i++)
#define int long long
using namespace std;

int n;
vector<int> et[50];
int m;
int u[20], v[20];
int p2[51];

vector<bool> isFill[50];
int depth[50];
int parent[50];
int parentId[50];

void dfs(int p, int v, int dep) {
	depth[v] = dep;
	parent[v] = p;
	
	for (int i = 0; i < et[v].size(); i++) {
		int nv = et[v][i];
		if (nv == p) continue;
		parentId[nv] = i;
		dfs(v, nv, dep + 1);
	}
}

void Reset() {
	int i, j;
	rep(i, n) { rep(j, isFill[i].size()) isFill[i][j] = false; }
}

void Fill(int u, int v) {
	if (depth[u] < depth[v]) swap(u, v);
	
	int du = depth[u];
	int dv = depth[v];
	
	//cout << "Fill(" << u << ", " << v << ")" << endl;
	//cout << "du = " << du << ", dv = " << dv << endl;
	
	while (du > dv) {
		isFill[parent[u]][parentId[u]] = true;
		//cout << "u, parent[u], parentId[u] = " << u << ", " << parent[u] << ", " << parentId[u] << endl;
		u = parent[u];
		du--;
	}
	
	while (u != v) {
		isFill[parent[u]][parentId[u]] = true;
		isFill[parent[v]][parentId[v]] = true;
		u = parent[u];
		v = parent[v];
	}
}

signed main() {
	int i, j, k;
	
	cin >> n;
	rep(i, n - 1) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		et[a].push_back(b);
		et[b].push_back(a);
	}
	cin >> m;
	rep(i, m) {
		cin >> u[i] >> v[i];
		u[i]--;
		v[i]--;
	}
	
	dfs(-1, 0, 0);
	
	p2[0] = 1;
	rep(i, n) p2[i + 1] = p2[i] * 2;
	
	rep(i, n) isFill[i].resize(et[i].size());
	
	int ans = 0;
	rep(i, (1 << m)) {
		Reset();
		
		int bcnt = 0;
		rep(j, m) {
			if ((i >> j) & 1) {
				Fill(u[j], v[j]);
				bcnt++;
			}
		}
		
		int fillCnt = 0;
		rep(j, n) {
			rep(k, isFill[j].size()) {
				if (isFill[j][k]) fillCnt++;
			}
		}
		
		//cout << "i = " << i << ", fillCnt = " << fillCnt << endl;
		if (bcnt % 2 == 0) ans += p2[n - 1 - fillCnt];
		else ans -= p2[n - 1 - fillCnt];
	}
	
	cout << ans << endl;
	return 0;
}

Submission Info

Judge Result