問題描述

天平的兩邊有時(shí)不一定只能掛物品，還可以繼續(xù)掛著另一個(gè)天平，現(xiàn)在給你一些天平的情況和他們之間的連接關(guān)系，要求使得所有天平都能平衡所需物品的總重量最輕。

一個(gè)天平平衡當(dāng)且僅當(dāng)“左端點(diǎn)的重量 $\times$ 左端點(diǎn)到支點(diǎn)的距離 $=$ 右端點(diǎn)的重量 $\times$ 右端點(diǎn)到支點(diǎn)的距離。

輸入格式

第一行包含一個(gè) $N(N\le 100)$，表示天平的數(shù)量，天平編號(hào)為 $1$ 到 $N$。

接下來包含 $N$ 行描述天平的情況，每行 $4$ 個(gè)整數(shù) $P,Q,R,B$，$P$ 和 $Q$ 表示橫桿上支點(diǎn)到左邊的長(zhǎng)度與到右邊的距離的比例為 $P:Q$，$R$ 表示左邊懸掛的情況，如果 $R=0$ 說明懸掛的物品，否則表示左邊懸掛的是天平 $R$；$B$ 表示右邊的懸掛情況，如果 $B=0$ 表示右邊懸掛的是物品，否則右邊懸掛著天平 $B$。

對(duì)于所有的輸入，保證 $W\times L\le 2^{31}$，其中 $W$ 為最輕的物品重量，而 $L$ 為輸入中描述左右比例時(shí)出現(xiàn)的最大值。

輸出格式

輸出一個(gè)整數(shù)表示使得所有天平都平衡所需最輕的物品總重量。

樣例

樣例輸入1：

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

樣例輸出1：

40

數(shù)據(jù)范圍

對(duì)于所有數(shù)據(jù)，$N\le 100,W\times L<2^{31}$。

題解

考慮第 $i$ 個(gè)天平，假設(shè)左右最輕重量為 $W1,W2$，比例為 $L1:L2$，當(dāng)前需要左右放 $X$ 和 $Y$。
則 $X$ 和 $Y$ 需要滿足：$W1\times L1\times X=W2\times L2\times Y$。
移項(xiàng)可得：$\frac{X}{Y}=\frac{W2\times L2}{W1\times L1}$。
因此，天平重量最小，必須將 $\frac{x}{y}$ 化為最簡(jiǎn)分?jǐn)?shù)。
求出 $W2\times L2$ 和 $W1\times L1$ 的最大公因數(shù) $P$，$X=W2\times L2\times P$，$Y=W1\times L1\times P$。
重量為 $X\times W1+Y\times W2$。
處理時(shí)直接遞歸求解

#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;
}