The 36th ACM/ICPC Asia Regional Beijing Site Online Contest - B Eliminate Witches!

简单题，模拟展开即可。O（N）。

其实根据样例就很能看出来的，结点一定是从左到右出现的单词。

关键是怎么确定树的顺序。

想一下括号匹配，其实这基本就是个括号匹配的问题。

遇到 (  就把当前结点作为公共父节点，如果遇到 ) 就返回上一层的父节点。

特殊情况就是 “),” 和“)))”这种。我是特判了。因为我是记录了一个公共的父亲，如果遇到一个 ) 就用类似并查集，找到父亲的父亲。。。

中间细节部分很繁。。。细心点应该就可以了。

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x << 1 )
#define R(x) ( x << 1 | 1 )
#define FOR(i,s,t) for(int i=(s); i<(t); i++)
#define BUG puts("here!!!")
#define STOP system("pause")
#define file_r(x) freopen(x, "r", stdin)
#define file_w(x) freopen(x, "w", stdout)

using namespace std;

const int MAX = 1000010;
char s[MAX];

struct NODE{
	char s[150];
	int pre;
};

NODE a[50010];
vector<pair<int,int> > p;

int main()
{
	int ncases;
	
	scanf("%d", &ncases);
	
	while( ncases-- )
	{
		p.clear();
		scanf("%s", s);
		int len = strlen(s);
		int cnt = 0, l = 0;
		int f = 1, now;
		a[1].pre = 1;
		bool aaa = true;
		
		FOR(i, 0, len)
		{
			if( isalpha(s[i]) )
			{
				if( aaa )
				{
					aaa = false;
					cnt++;
					a[cnt].pre = f;
					p.push_back(make_pair(f, cnt));
				}
				a[cnt].s[l++] = s[i];
			}
			else
			{
				if( l != 0 )
					a[cnt].s[l] = '\0';
				aaa = true;
				a[cnt].pre = f;
				l = 0; 
				if( s[i] == '(' )
				{
					f = cnt;
				}
				if( s[i] == ',' )
				{
					p.push_back(make_pair(cnt, f));
				}
				if( s[i] == ')' )
				{
					p.push_back(make_pair(cnt, f));
					while( s[i+1] == ')' && i+1 < len)
					{
						p.push_back(make_pair(f, a[f].pre));
						f = a[f].pre;
						i++;
					}
					if( i+1 < len && s[i+1] == ',' )
					{
						p.push_back(make_pair(f, a[f].pre));
						f = a[f].pre;
						i++;
					}
				}
			}
		}
		if( l != 0 )
			a[cnt].s[l] = '\0';
		
		printf("%d\n", cnt);
		FOR(i, 1, cnt+1)
			printf("%s\n", a[i].s);
		
		FOR(i, 1, p.size())
			printf("%d %d\n", p[i].first, p[i].second);
		
		printf("\n");
	}

return 0;
}