声明：同样是参考照抄hyh学长的代码！（有问题我马上删这篇emm
题目链接：http://118.190.20.162/view.page?gpid=T77
题面：
这棵树的样子（同样是来自学长的图）
题解：
要解决的两个关键问题：
第一个是语义解析，也就是把树构造出来。这个也是用指针实现。这个树的构建比起上一题来更简单，因为节点实际上都是一样的，而上一题（JSON查询）则要分为对象和字符串两种。
这里要注意parent的指向，用一个堆实现查找parent。
第二个是查询。要查询符合条件的路径。这里稍微需要一些思路。
如果直接从上往下找，那这个复杂度最坏的情况是n^2的。但是在实际情况中（也是题目给的提示），从后往前找会大大减少情况（可以排除很多情况）。
处理细节很重要呀！同样也要想清楚每个函数的作用！
#include<bits/stdc++.h>
using namespace std; struct tree
{
int id, dots;
string tag, name;
tree* parent; tree(int id, int dots, string tag, string name): id(id), dots(dots), tag(tag), name(name) ,parent() {}//parent的初始化
}; void split(const string &str, vector<string> &out)
{
string last;
last.clear();
for (int i = ; i < str.size(); i++)
{
if(str[i] == ' ')
{
out.push_back(last);
last.clear();
}
else last+=str[i];
}
out.push_back(last);
} bool equal_ignore_case(const string &a,const string &b)
{
if(a.size() != b.size()) return ;
for(int i = ; i < a.size(); i++)
{
if(tolower(a[i]) != tolower(b[i])) return ;
}
return ;
} bool apply(string str, tree *t)
{
if(str[] == '#') return str == t->name;
else return equal_ignore_case(str, t->tag);
} int main()
{
// freopen("a.in","r",stdin);
int n,m;
string line;
scanf("%d%d",&n,&m); getline(cin,line); vector<tree *> nodes;
stack<tree *> sta; for(int i = ; i <= n; i++)
{
getline(cin, line); int dots=;
while (line[dots] == '.') dots++; string tag, name;
stringstream ss(line.substr(dots));
ss >> tag >> name; tree *now = new tree(i, dots, tag, name);
if(!sta.empty())
{
tree* top;
while (top = sta.top(), top->dots >= dots)
sta.pop();
now->parent = top;
}
sta.push(now);
nodes.push_back(now);
}
/*
for(int i = 0; i < nodes.size(); i++)
{
printf("id = %d dots = %d ",nodes[i]->id,nodes[i]->dots);
cout << "tag = " << nodes[i]->tag << " name = " << nodes[i]->name ;
if(nodes[i]->parent) cout << " parent = " << nodes[i]->parent->id << endl;
else cout << endl;
}
*/
vector<string> selector;
vector<int> ans;
ans.clear();
while (m--)
{
getline(cin, line);
selector.clear();
split(line, selector);
// printf("************* m = %d\n",m);
// for(int i = 0 ; i < selector.size(); i++)
// cout << selector[i] << endl;
ans.clear();
for (int i = ; i < nodes.size(); i++)
{
if (apply(selector.back(),nodes[i]))
{
tree *t = nodes[i];
int sl = selector.size()-;
while(t && sl>=)
{
if(apply(selector[sl],t)) sl--;
t = t->parent; }
if (sl == -)
ans.push_back(nodes[i]->id);
}
}
printf("%d ",ans.size());
for (int i = ; i < ans.size() ; i++)
printf("%d ",ans[i]);
printf("\n");
} return ;
}
更新一下代码（刷题的时候又遇到了这题，重新做了一遍（并没有什么区别..写码习惯不同））
#include<bits/stdc++.h>
using namespace std; struct tree{
string tag,name;
int dots;
tree* parent; tree(int dots, string tag, string name): dots(dots),tag(tag),name(name),parent() {}
}; bool check(const string &s,tree* t)
{
if(s[]=='#') return s == t->name;
else
{
if(s.size()!=t->tag.size()) return ;
for(int i=;i<s.size();i++)
{
if(tolower(s[i])!=tolower(t->tag[i])) return ;
}
return ;
}
} void divide(const string &s,vector<string> &vec)
{
string token;
token.clear();
vec.clear();
for(int i=;i<s.size();i++)
{
if(s[i]==' ')
{
vec.push_back(token);
token.clear();
}
else token+=s[i];
}
vec.push_back(token);
} int main()
{
//freopen("a.in","r",stdin);
int n,m;
scanf("%d%d",&n,&m);
string line;
getline(cin,line); vector<tree* > nodes;
nodes.clear();
stack<tree* > sta;
while(!sta.empty()) sta.pop(); for(int i=;i<=n;i++)
{
getline(cin,line); int dots=;
while(line[dots]=='.') dots++; string tag,name;
stringstream ss(line.substr(dots));
ss >> tag >> name; tree* now = new tree(dots, tag, name); if(!sta.empty())
{
tree* top;
while( top = sta.top() , top->dots >= dots )
sta.pop();
now->parent = top;
}
sta.push(now);
nodes.push_back(now);
} // for(int i=0;i<nodes.size();i++)
// {
// cout << "id = " << i << " tag = " << nodes[i]->tag << " name = " << nodes[i]->name ;
// if(nodes[i]->parent) cout<< " parent = " << nodes[i]->parent->tag;
// cout << endl;
// } vector<string> sel;
vector<int> ans; while(m--)
{
getline(cin,line);
divide(line,sel); ans.clear(); for(int i=;i<nodes.size();i++)
{
int sl=sel.size()-;
if(check(sel[sl],nodes[i]))
{
tree* t=nodes[i]->parent;
sl--;
while(t && sl>=)
{
if(check(sel[sl],t)) sl--;
t=t->parent;
}
if(sl==-) ans.push_back(i+);
}
}
printf("%d ",ans.size());
for(int i=;i<ans.size();i++) printf("%d ",ans[i]);printf("\n");
}
return ;
}