[exercise-5] (UVA 839) not so mobile (balance)

Translate ：

Enter a tree scale , Judge whether it is balanced according to the principle of equal moment . The so-called equal moment , Namely W1D1 = W2D2, among W1 and W2 Are the weights of the left and right weights ,D For distance .
Recursion （ Preface ） Mode input ： The format of each balance is W1 D1 W2 D2, When W1 or W2 by 0 when , It means that we should “ Weights ” It's actually a balance , Next, I will describe the scale . When W1=W2=0 when , I will first describe the left balance , Then there is the right balance .

recursive .

AC Code ：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
const ll mod = 1e9+7;
int solve(int &w)
{
    
	int w1,d1,w2,d2;
	int x1=1,x2=1;
	cin>>w1>>d1>>w2>>d2;
	if(!w1)	x1 = solve(w1);
	if(!w2) x2 = solve(w2);
	w = w1+w2;
	return x1 && x2 && (w1 * d1 == w2 * d2);
}
int main()
{
    
	int n,w;
	cin>>n;
	while(n--)
	{
    
		if(solve(w))
			cout<<"YES"<<endl;
		else
			cout<<"NO"<<endl;
		cout<<endl;
	}
}

to x1 and x2 The assignment is 1 It's because on the last floor , He has no left-right balance , So the default is 1.
Because it is preordered recursion , So our input is first root, then left and then right . According to the introduction of the topic, you can also know , It must be a balanced binary tree .
At first, I thought I could not add w, It turned out ,w Must be added and participate in recursion , If not , Then only the bottom layer can complete the calculation

Like in the picture above , Only 1 * 1 = 1 * 1 and 2 * 4 = 4 * 2 and 3* 2 = 6 * 1 It can be calculated if you don't add w Words .
After adding, the sum of the following two balls will be returned each time, so you can find out whether the two balances are balanced . And so on , Recursion completes .