2 shunfurh shunfurh 于 2017.11.26 00:18 提问

Same or not

Problem Description
Everyone konws how to traveling a tree using the DFS strategy. But we also know that there are many ways to do so. For example, giving a tree as the following picture, we may get three ways: 010011, 001101, 01010011. 0 stands for the down operation while 1 means the up operation.
Now we make a constraint: if one node has k direct childs, you can visit a node at most 2*k times, if k == 0, you can visit it only once, in the example, the root has two direct child. Like the example, you can only get two ways: 010011, 001101. Because the way 01010011 will visit the node in yellow four times.
Here is the problem: ACboy drawed a tree, but is not very nice, so he won't show you the picture. Instread he will give you two strings indicating that the ways to travel the tree. Of cource, the strings will only contain 0 and 1. And your mission is to tell whether ACboy is telling the truth. For example, he drawed a picture as the following, if he give you 010011 and 001101, then he is telling the truth, but if he give you 010011 and 01010011, you konw that he is telling a lie.

Input
On the first line of input is a single positive integer n, telling the number of test scenarios to follow.Each test case consists of two lines, each containing a string of the characters '0' and '1' of length at most 3000, both describing a way to travel the tree.

Output
For each test case output a line containing the word "True" or the word "False", depending on whether ACboy is telling the truth.

Sample Input
2
010011
001101
010011
01010011

Sample Output
True
False

2个回答

caozhy
caozhy   Ds   Rxr 2018.03.27 23:42
已采纳
swchlz811
swchlz811   2018.02.15 01:50

Everyone konws how to traveling a tree using the DFS strategy. But we also know that there are many ways to do so. For example, giving a tree as the following picture, we may get three ways: 010011, 001101, 01010011. 0 stands for the down operation while 1 means the up operation.

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!