AOJ1001とか

解法思いついたけど提出してみたらWA…と思ったらバグがあっただけでした。
久しぶりに閃いたのでとりあえず書いただけ。

ちなみにこの問題、閃いたのはこの顔文字のおかげ→('ω')



import java.io.IOException;
import java.io.StringReader;
import java.util.Scanner;

public class Main
{
	static final Scanner s = new Scanner(System.in);

	public static void main(String[] args)
	{
		while(s.hasNextLine())
		{
			String[] str = s.nextLine().split(" ");
			if(str[0].charAt(0)=='i') System.out.println(BinaryTree.intersection(BinaryTree.parse(str[1]), BinaryTree.parse(str[2])));
			else if(str[0].charAt(0)=='u') System.out.println(BinaryTree.union(BinaryTree.parse(str[1]), BinaryTree.parse(str[2])));
		}
	}
}
class BinaryTree
{
	public static Node parse(String str)
	{
		try
		{
			StringReader r = new StringReader(str);
			r.read();
			Node root = new Node();
			Node current = root;
			while(true)
			{
				int ch = r.read();
				if(ch==-1) break;
				if(ch=='(')
				{
					current = current.setLeft(new Node());
				}
				else if(ch==')')
				{
					current = current.parent;
				}
				else if(ch==',')
				{
					int next = r.read();
					if(next=='(')
					{
						current = current.setRight(new Node());
					}
					else if(next==')')
					{
						current = current.parent;
					}
					else throw new IllegalArgumentException();
				}
				else throw new IllegalArgumentException();
			}
			return root;
		}
		catch(IOException e)
		{
			throw new InternalError();
		}
	}
	public static Node copy(Node a)
	{
		Node copy = new Node();
		copy0(a, copy);
		return copy;
	}
	private static void copy0(Node a, Node current)
	{
		if(a.left!=null)
			copy0(a.left, current.setLeft(new Node()));
		if(a.right!=null)
			copy0(a.right, current.setRight(new Node()));
	}
	public static Node intersection(Node a, Node b)
	{
		Node intersection = new Node();
		intersection0(a, b, intersection);
		return intersection;
	}
	private static void intersection0(Node a, Node b, Node current)
	{
		if(a.left!=null && b.left!=null)
			intersection0(a.left, b.left, current.setLeft(new Node()));
		if(a.right!=null && b.right!=null)
			intersection0(a.right, b.right, current.setRight(new Node()));
	}
	public static Node union(Node a, Node b)
	{
		Node union = new Node();
		union0(a, b, union);
		return union;
	}
	private static void union0(Node a, Node b, Node current)
	{
		if(a.left!=null && b.left!=null)
			union0(a.left, b.left, current.setLeft(new Node()));
		else if(a.left!=null)
			current.left = copy(a.left);
		else if(b.left!=null)
			current.left = copy(b.left);
		if(a.right!=null && b.right!=null)
			union0(a.right, b.right, current.setRight(new Node()));
		else if(a.right!=null)
			current.right = copy(a.right);
		else if(b.right!=null)
			current.right = copy(b.right);
	}

	public static class Node
	{
		private Node parent, left, right;

		public Node setLeft(Node left)
		{
			this.left = left;
			left.parent = this;
			return left;
		}
		public Node setRight(Node right)
		{
			this.right = right;
			right.parent = this;
			return right;
		}
		@Override
		public String toString()
		{
			return '(' + (left==null ? "" : left.toString()) + ',' + (right==null ? "" : right.toString()) + ')';
		}
	}
}


オブジェクト指向なんてなかったよ
無駄が多すぎるけどまぁ仕方ない