1929E - Sasha and the Happy Tree Cutting - CodeForces Solution

/*
 * frash
 * 11:16
 * 2/15/2024
*/

#include <bits/stdc++.h>
using namespace std;

#define vt vector
#define ll long long
#define ld long double
#define fs first
#define sc second

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define all(a) begin(a), end(a)
#define rall(a) rbegin(a), rend(a)
#define endl '\n'
#define len(x) ((int)x.size())
#define obt(a, b) get<b>(a)
#define EACH(i, j) for(auto& i : j)

// https://trap.jp/post/1224/
#define FOR1(a) for(int i=0; i<a; ++i)
#define FOR2(a, b) for(int a=0; a<b; ++a)
#define FOR3(a, b, c) for(int a=b; a<c; ++a)
#define FOR4(a, b, c, d) for(int a=b; a<c; a+=d)
#define overload4(a, b, c, d, e, ...) e
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)

ll mdlo(ll n, ll m){ return (n % m + m) % m; }
template<typename T, typename U> void chmax(T& a, U b){ a = (b > a ? b : a); }
template<typename T, typename U> void chmin(T& a, U b){ a = (b < a ? b : a); }
int msb(ll x){ if(x) return 63 - __builtin_clzll(x); return -1; }
int lsb(ll x){ if(x) return __builtin_ctzll(x); return -1; }

ll power(ll a, ll b, ll m = 1222333444555666777){
	ll ret = 1;
	for(; b; a = a * a % m, b >>= 1) if(b & 1) ret = ret * a % m;
	return ret;
}
ll gcd(ll a, ll b){
	while(a)
		b %= a, swap(a, b);
	return b;
}
ll gcd(ll a, ll b, ll& x, ll& y){
	if(!a){ x = 0, y = 1; return b; }
	ll res = gcd(b % a, a, x, y), ty = y;
	y = x,  x = ty - b / a * x;
	return res;
}

const ll INF = 1e18, NINF = -INF;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

string to_string(char a){ return "'"+string(1, a)+"'"; }
string to_string(string a){ return '"'+a+'"'; }
string to_string(bool a){ return a?"True":"False"; }
//template<ll A> string to_string(Modular<A> a) { return to_string(a.x); }
template<typename A, typename B> string to_string(pair<A,B>&p){ return "("+to_string(p.first)+", "+to_string(p.second)+")"; }
template<typename T> string to_string(T& a){
	bool f = 1; string ret = "{";
	for(auto& i:a){
		if(!f) ret += ", "; ret += to_string(i), f = 0;
	} return ret + "}";
}
void dbug(){ cerr << endl; }
template<typename R, typename... T> void dbug(R a, T... other){ cerr << " " + to_string(a); dbug(other...); }

#ifdef ONLINE
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", dbug(__VA_ARGS__);
#else
#define debug(...)
#endif

const int N = 1e5;

vt<int> vis[N + 1];
int prv[N + 1], prvnode[N + 1];
vt<int> adj[N + 1];
vt<int> num[N + 1];

void dfs(int u, int p){
	FOR(i, 0, len(adj[u])){
		int v = adj[u][i], idx = num[u][i];
		if(v != p){
			prv[v] = idx;
			dfs(v, u);
		}
	}

	prvnode[u] = p;
}

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

	FOR(i, 0, n - 1){
		int u, v;
		cin >> u >> v;
		adj[u].pb(v);
		num[u].pb(i);
		adj[v].pb(u);
		num[v].pb(i);
	}

	int k;
	cin >> k;

	FOR(i, 0, n - 1)
		vis[i].resize(k);

	FOR(i, 0, k){
		int u, v;
		cin >> u >> v;
		dfs(u, 0);
		int curr = v;
		while(curr != u){
			vis[prv[curr]][i] = 1;
			curr = prvnode[curr];
		}
	}

	set<int> val;
	FOR(i, 0, n - 1){
		int curr = 0;
		FOR(j, 0, k)
			curr += (1 << j) * vis[i][j];
		val.insert(curr);
	}

	vt<int> v;
	EACH(i, val)
		v.pb(i);
	int m = len(v);
	vt<int> dp(1 << k, 50), temp(1 << k, 50);
	dp[0] = 0;
	FOR(i, 0, m){
		FOR(j, 0, 1 << k){
			int k = j | v[i];
			chmin(temp[k], dp[j] + 1);
			chmin(temp[j], dp[j]);
		}
		swap(dp, temp);
		fill(all(temp), 50);
	}

	cout << dp[(1 << k) - 1] << endl;

	for(int i = 0; i <= n; ++i)
		adj[i].clear(), num[i].clear(), vis[i].clear();
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(20);

	int tt = 1;
	cin >> tt;
	while(tt--) solve();
}