[树] 最轻的天平

问题描述

天平的两边有时不一定只能挂物品，还可以继续挂着另一个天平，现在给你一些天平的情况和他们之间的连接关系，要求使得所有天平都能平衡所需物品的总重量最轻。

一个天平平衡当且仅当“左端点的重量 $\times$ 左端点到支点的距离 $=$ 右端点的重量 $\times$ 右端点到支点的距离。

输入格式

第一行包含一个 $N(N\le 100)$，表示天平的数量，天平编号为 $1$ 到 $N$。

接下来包含 $N$ 行描述天平的情况，每行 $4$ 个整数 $P,Q,R,B$，$P$ 和 $Q$ 表示横杆上支点到左边的长度与到右边的距离的比例为 $P:Q$，$R$ 表示左边悬挂的情况，如果 $R=0$ 说明悬挂的物品，否则表示左边悬挂的是天平 $R$；$B$ 表示右边的悬挂情况，如果 $B=0$ 表示右边悬挂的是物品，否则右边悬挂着天平 $B$。

对于所有的输入，保证 $W\times L\le 2^{31}$，其中 $W$ 为最轻的物品重量，而 $L$ 为输入中描述左右比例时出现的最大值。

输出格式

输出一个整数表示使得所有天平都平衡所需最轻的物品总重量。

样例

样例输入1：

4
3 2 0 4
1 3 0 0
4 4 2 1
2 2 0 0

样例输出1：

40

数据范围

对于所有数据，$N\le 100,W\times L<2^{31}$。

题解

考虑第 $i$ 个天平，假设左右最轻重量为 $W1,W2$，比例为 $L1:L2$，当前需要左右放 $X$ 和 $Y$。
则 $X$ 和 $Y$ 需要满足：$W1\times L1\times X=W2\times L2\times Y$。
移项可得：$\frac{X}{Y}=\frac{W2\times L2}{W1\times L1}$。
因此，天平重量最小，必须将 $\frac{x}{y}$ 化为最简分数。
求出 $W2\times L2$ 和 $W1\times L1$ 的最大公因数 $P$，$X=W2\times L2\times P$，$Y=W1\times L1\times P$。
重量为 $X\times W1+Y\times W2$。
处理时直接递归求解

#define int long long
int dfs(int x){if(x == 0){//边界return 1;}int t1 = dfs(l[x]), t2 = dfs(r[x]);int t = __gcd(a[x] * t1, b[x] * t2);return t1 * a[x] * t2 / t + t2 * b[x] * t1 / t;
}
signed main(){scanf("%d", &n);for(int i = 1; i <= n; ++ i){scanf("%d %d %d %d", &a[i], &b[i], &l[i], &r[i]);f[l[i]] = 1;f[r[i]] = 1;}int rt = 0;for(int i = 1; i <= n; ++ i){if(!f[i]){rt = i;break;}}printf("%lld", dfs(rt));return 0;
}