题目分析

我们需要计算家族成员之间的血缘关系系数，其中血缘关系只能从双亲传递到后代。给定双亲关系，求所有成员之间的血缘关系系数 $p[i][j]$，并保证对称性 $p[j][i] = p[i][j]$。

解题思路

1. 递推关系定义：

   • 设成员 $f$ 和 $m$ 是成员 $\text{son}$ 的双亲，则 $\text{son}$ 与双亲的血缘关系为：
     [ p[\text{son}][f] = p[\text{son}][m] = 0.5 + 0.5 \times p[f][m] ]
     表示 $\text{son}$ 从双亲各继承一半血缘，并额外叠加双亲之间的血缘关系。

   • 对于其他成员 $j$（非双亲），$\text{son}$ 与 $j$ 的血缘关系为：
     [ p[\text{son}][j] = 0.5 \times \left( p[f][j] + p[m][j] \right) ]
     表示 $\text{son}$ 的血缘关系是双亲与 $j$ 关系的平均值。

2. 对称性处理：

   • 由于血缘关系是双向的，需保证 $p[i][j] = p[j][i]$。计算时仅需维护上三角或下三角矩阵。

3. 初始化与递推顺序：

   • 初始化所有成员与自身的血缘关系为 $1$，即 $p[i][i] = 1$。
   • 按家族树拓扑顺序递推（如从祖先到后代），确保计算子节点时双亲关系已确定。

关键点

• 高精度处理：
  • 血缘关系系数可能涉及分数累加，需用分数运算或高精度浮点数避免精度丢失。
• 递推依赖：
  • 子节点的血缘关系完全依赖双亲，需严格按拓扑顺序计算。

复杂度分析

• 时间复杂度：
  • 假设家族成员数为 $n$，每对关系需 $O(1)$ 时间计算，总复杂度为 $O(n^2)$。
• 空间复杂度：
  • 存储血缘关系矩阵需 $O(n^2)$ 空间。

#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstring>
using namespace std;

struct mes {
	int son, nxt;
	mes() : son(0), nxt(0) {}
};

const int maxn = 650;
int head[maxn];
double p[maxn][maxn];
mes s[2 * maxn];
int fa[maxn][2];
int n, k, m;
int vis[maxn];
int que[maxn];

void addedge(int f, int t, int ind) {
	s[ind].nxt = head[f];
	s[ind].son = t;
	head[f] = ind;
}

void init() {
	memset(head, -1, sizeof(head));
	for (int i = 0; i < maxn; ++i) {
		for (int j = 0; j < maxn; ++j) {
			p[i][j] = 0.0;
		}
	}
	cin >> n >> k;
	for (int i = 0; i < k; ++i) {
		int son, f, mth;
		cin >> son >> f >> mth;
		addedge(f, son, 2 * i);
		addedge(mth, son, 2 * i + 1);
		fa[son][0] = f;
		fa[son][1] = mth;
	}
	for (int i = 1; i <= n; ++i) {
		p[i][i] = 1.0;
	}
}

void calc() {
	int front = 0, tail = 0;
	const double mul = 0.5;
	for (int i = 1; i <= n; ++i) {
		if (fa[i][0] == 0 && fa[i][1] == 0 && vis[i] == 0) {
			que[tail++] = i;
			vis[i] = 1;
		}
	}
	while (front < tail) {
		int tp = que[front++];
		vis[tp] = 2;
		int f = fa[tp][0], m = fa[tp][1];
		if (f != 0 && m != 0) {
			double val = (p[f][m] + 1.0) * 0.5;
			p[tp][f] = val;
			p[tp][m] = val;
			p[f][tp] = val;
			p[m][tp] = val;
			
			for (int i = 1; i <= n; ++i) {
				if (i != f && i != tp && i != m) {
					p[i][tp] += (p[i][f] + p[i][m]) * 0.5;
					p[tp][i] = p[i][tp];
				}
			}
		}
		
		for (int sp = head[tp]; sp != -1; sp = s[sp].nxt) {
			int son = s[sp].son;
			if (vis[son] != 0) continue;
			if (vis[fa[son][0]] == 2 && vis[fa[son][1]] == 2) {
				que[tail++] = son;
				vis[son] = 1;
			}
		}
	}
}

void show() {
	cin >> m;
	for (int i = 0; i < m; ++i) {
		int f, t;
		cin >> f >> t;
		double val = p[t][f] * 100.0;
		
		ostringstream oss;
		oss << fixed << setprecision(10) << val;
		string ans = oss.str();
		
		size_t last_non_zero = ans.find_last_not_of('0');
		if (last_non_zero != string::npos) {
			ans = ans.substr(0, last_non_zero + 1);
		} else {
			ans = "0";
		}
		
		if (!ans.empty() && ans.back() == '.') {
			ans.pop_back();
		}
		
		cout << ans << "%" << endl;
	}
}

int main() {
	init();
	calc();
	show();
	return 0;
}