很坑的一道题，读了半天才读懂题，手忙脚乱的写完（套上模板+修改模板），然后RE到死……
题意：
题面上告诉了我们这是一棵二叉树，然后告诉了我们它的先序遍历，然后，没了……没了！
反复读题，终于在偶然间注意到了这一句——"Not only that, when numbering the rooms, they always number the room number from the east-most position to the west."
它告诉我们，东边的点总是比西边的点小——也就是说，这个树的中序遍历是从1到n的一个等差数列……
输入：
首行输入一个整数t，表示有t组数据；
接下来每组数据首行一个整数n，表示有这棵树有n个节点。
接下来一行有n个整数，表示这棵树的先序遍历。
接下来一行一个整数m，表示m次查询。
接下来一行有m个整数，表示每次查询的点。
输出：
每次查询输出从根节点到查询节点的路径，路径中，每次向左输出'E'，每次向右输出'W'。
解题思路：
套上模板，建立起这棵树，同时用一个fm[]数组讲每个节点的父节点记录下来。然后查询的时候使用就行了。
但是有两点需要注意：
1. 由于我是使用指针建立的树，所以每用完一组数据都要记得释放内存！
2. 每次第二组数据的根节点也许在第一组数据中不是根节点，所以要记得将根节点的父节点fm[root]置为0。我的现场赛名额啊……因此离我而去T_T，555555……
不说了，说多了都是泪。。。。。
上代码——
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include <cmath>
#include <algorithm>
using namespace std; struct Node
{
int c;
Node *left;
Node *right;
}; int fm[];
int t, n, m;
char dis[];
int pree[],ine[]; Node* BuildTree(int *pre, int *in, int length) //建树
{
if(length == ) return NULL;
Node* node = (Node*) malloc(sizeof(Node));
node->c = pre[];
int rootindex = -;
for(int i = ;i < length;i++)
{
if(in[i] == pre[])
{
rootindex = i;
break;
}
}
node->left = BuildTree(pre+,in,rootindex);//left
node->right = BuildTree(pre++rootindex,in+rootindex+,length-rootindex-);//right
return node;
} void print(Node *root) //记录父节点
{
if(root != NULL)
{
if(root->left != NULL) fm[root->left->c] = (root->c)*;
print(root->left);
if(root->right != NULL) fm[root->right->c] = (root->c)*+;
print(root->right);
}
} void dfs(Node* root) //释放内存
{
if(root != NULL)
{
if(root->left != NULL) dfs(root->left);
if(root->right != NULL) dfs(root->right);
free(root);
}
} int main()
{
//freopen("test.in", "r", stdin);
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(int i = ; i < n; i++)
{
scanf("%d", &pree[i]);
ine[i] = i+;
}
Node *root = BuildTree(pree, ine, n) ;
fm[root->c] = ; //就是这里，坑死我了……我@#￥%^&*!
print(root);
scanf("%d",&m);
for(int i = ; i < m; i++)
{
int mid;
scanf("%d", &mid);
int k = ;
while(fm[mid] != )
{
if(fm[mid]% == ) dis[k] = 'W';
else dis[k] = 'E';
mid = fm[mid]/;
k++;
}
for(int j = k-; j >=; j--) printf("%c", dis[j]); //输出路径
printf("\n");
}
dfs(root);
}
return ;
}