https://www.hackerrank.com/contests/university-codesprint-2/challenges/the-story-of-a-tree

$n$個の頂点の木が与えられる．Bobはランダムでrootを選ぶ．Aliceの$parent(v_i) = u_i$であるか，という$g$個の質問が，ボブが選んだ木に対して$k$個以上正解しているかの確率を求める．

愚直に求める場合は，ボブが選んだ木全てに対して，つまりrootが$0 \sim n-1$である全ての木に対して，Aliceの質問が$k$個以上正解しているかを求める．これは$O(ng)$となり間に合わない．

親子関係が変わるのは，rootと隣接している頂点$v$とrootを変更するとき，つまり $$ \begin{eqnarray} parent[root] &=& -1\\
parent[v] &=& root \end{eqnarray} $$ の場合に$v$をrootに変更するときは， $$ \begin{eqnarray} parent[root] &=& v\\
parent[v] &=& -1 \end{eqnarray} $$ とし，親子関係が変わるのは$2$点のみである．他は変更する必要がない．

まず適当にrootを$0$にして，親子関係を構築し，そこからrootをdfsでrootを変更していく．現在のrootを$cur$，次にrootに変更しようと考えている頂点を$to$とすると，$parent[to] = cur$の関係が失われ，$parent[cur] = to$の関係が生まれる．これがAliceの質問に入っているかを見ればよい．Aliceの質問を満たしている親子関係をsetで持ったので$O(n log(g))$

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,k,n) for(int i=k;i<(int)(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
#define fi first
#define se second
#define MAX_N 200005

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int par[MAX_N];
vector<int> G[MAX_N];

void dfs(int cur, int pre) {
	par[cur] = pre;

	rep(i, G[cur].size()) {
		int to = G[cur][i];
		if(to == pre) continue;
		dfs(to, cur);
	}
}

int ok = 0, K = 0;
vector<int> a, b;
set<P> st, input;

void dfs2(int cur, int pre) {
	if(st.size() >= K) ok++;

	rep(i, G[cur].size()) {
		int to = G[cur][i];
		if(to == pre) continue;

		// root - change (cur, to)
		par[cur] = to;
		par[to] = -1;

		P inP = mp(cur, to);
		P outP = mp(to, cur);

		bool in = false, out = false;
		if(st.find(outP) != st.end()) {
			out = true;
			st.erase(outP);
		}

		if(input.find(inP) != input.end() && st.find(inP) == st.end()) {
			in = true;
			st.insert(inP);
		}

		dfs2(to, cur);

		if(out) {
			st.insert(outP);
		}

		if(in) {
			st.erase(inP);
		}

		par[cur] = -1;
		par[to] = cur;
	}
}

int main() {
	int q;
	cin >> q;

	rep(qq, q) {
		int n;
		cin >> n;

		rep(i, MAX_N) G[i].clear();
		rep(i, n - 1) {
			int u, v;
			cin >> u >> v;

			u--; v--;
			G[u].push_back(v);
			G[v].push_back(u);
		}

		int g, k;
		cin >> g >> k;
		K = k;

		a.clear(); a.resize(g);
		b.clear(); b.resize(g);

		rep(i, g) {
			cin >> a[i] >> b[i];
			a[i]--; b[i]--;
		}

		rep(i, MAX_N) par[i] = -1;
		dfs(0, -1);

		st.clear(); input.clear();
		rep(i, g) {
			P p = mp(b[i], a[i]);
			input.insert(p);
			if(par[b[i]] == a[i]) st.insert(p);
		}

		ok = 0;
		dfs2(0, -1);

		int d = __gcd(ok, n);

		int x = ok / d;
		int y = n / d;

		cout << x << "/" << y << endl;

		// if(x == 0) cout << 0 << endl;
		// else if(x == y) cout << 1 << endl;
		// else cout << x << "/" << y << endl;
	}

	return 0;
}

余りの読解力の無さでp/qと$q$のqの区別が分からず，ゲームを通しての確率を求めるものだと勘違いしていた．また0/1が解となる時には0を，1/1が解となる時には1を出力すると勘違いしてしまい，WAを重ねてしまった．