【NOI导刊2009普及(6)】最轻的天平（gcd）

题目描述

天平的两边有时不一定只能挂物品，还可以继续挂着另一个天平，现在给你一些天平的情
况和它们之间的链接关系，要求使得所有天平都能平衡所需物品的总重量最轻，一个天平平衡
当且仅当“左端点的重量*左端点到支点的距离=右端点的重量*右端点到支点的距离”。注意题
目中的输入保证这些天平构成一个整体。

输入

第 1 行:包含一个整数 N（ N≤100），表示天平的数量，编号为 1 到 N。
接下来 N 行描述天平的情况，每行 4 个整数 P,Q,R,B， P 和 Q 表示横杆上支点到左边的长度与到
右边的距离的比例为 P:Q， R 表示左边悬挂的情况，如果 R=0 说明悬挂的是物品，否则表示左边
悬挂的是天平 R； B 表示右边悬挂的情况，如果 B=0 说明悬挂的是物品，否则表示右边悬挂的是
天平 B。
对于所有输入，保证 W*L<2^31,其中 W 为最轻的天平重量，而 L 为输入中描述左右比例时出现
的最大值。

输出

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

要使得 l左*G左=l右*G右，那么这个天平最轻重量就是 l左*G左，l右*G右 的最小公倍数，即 l左*G左*l右*G右 / gcd(l左*G左,l右*G右)。然后二叉树递归即可。

#include <algorithm>
#include <cstdio>

struct tinp{
    long long p,q,r,b;
}a[101];

int n,root;
long long f[101];
bool p[101];

long long dfs(int x){
    int l=a[x].r,r=a[x].b;
    long long lmin=1,rmin=1;
    if(l)lmin=dfs(l);
    if(r)rmin=dfs(r);
    int ans=lmin*a[x].p*rmin*a[x].q/std::__gcd(lmin*a[x].p,rmin*a[x].q);
    return ans/a[x].p+ans/a[x].q; 
}

int main(void){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld%lld%lld%lld",&a[i].p,&a[i].q,&a[i].r,&a[i].b);
        p[a[i].r]=true;
        p[a[i].b]=true;
    }
    for(int i=1;i<=n;++i){
        if(!p[i]){
            root=i;
            break;
        }
    }
    printf("%lld ",dfs(root));
}