题目思路
It is guaranteed that both A and B in the statements(语句中) are in the tree.
有这句就不用判断A B 是不是不是树中的结点,访问时会有段错误
-
siblings判断:存完l[root]后再存l[root]的父节点是root
l[root]=build(il,k-1,pl,pl+k-il-1); p[l[root]]=root;
-
full tree判断,除根节点外,每层结点数是偶数v【N】:
void dfs(int root,int depth)
{
v[depth].push_back(root);
h[root]=depth; 深度数组h【】判断是否同一层
if(l.count(root)) dfs(l[root],depth+1);
if(r.count(root)) dfs(r[root],depth+1);
}
错误
- sscanf t1前忘了写&————程序卡住但不报错
- 树中每个节点的权值各不相同,取值范围 [1,1000]
N不能开到35,开到1010就对了
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int post[N],in[N],p[N],h[N];
unordered_map<int,int> pos,l,r;
vector<int> v[N];
int build(int il,int ir,int pl,int pr)
{
int root=post[pr];
int k=pos[root];//8
if(k>il){
l[root]=build(il,k-1,pl,pl+k-il-1);
p[l[root]]=root;
}
if(k<ir)
{
r[root]=build(k+1,ir,pl+k-il,pr-1);
p[r[root]]=root;
}
return root;
}
void dfs(int root,int depth)
{
v[depth].push_back(root);
h[root]=depth;
if(l.count(root)) dfs(l[root],depth+1);
if(r.count(root)) dfs(r[root],depth+1);
}
int main()
{
//freopen("1.txt","r",stdin);
cin>>n;
for(int i=1;i<=n;i++) cin>>post[i];
for(int i=1;i<=n;i++)
{
cin>>in[i];pos[in[i]]=i;
}
int root =build(1,n,1,n);
dfs(root,1);
bool full_tree=1;
for(int i=2;i<N;i++)//除根以为,每层应该有偶数个结点
if(v[i].size()%2!=0)
{
full_tree=false;
break;
}
cin>>m;
getchar();
while(m--)
{
string s;int t1,t2;
getline(cin,s);
if(s.back()=='t')
{
sscanf(s.c_str(),"%d is the root",&t1);
if(t1==root) puts("Yes");
else puts("No");
}
else if(s.back()=='s')
{
sscanf(s.c_str(),"%d and %d are siblings",&t1,&t2);
if(p[t1]==p[t2]) puts("Yes");
else puts("No");
}
else if(s.back()=='l')
{
sscanf(s.c_str(),"%d and %d are on the same level",&t1,&t2);
if(h[t1]==h[t2]) puts("Yes");
else puts("No");
}else if(s.back()=='e')
{
if(full_tree) puts("Yes");
else puts("No");
}else if(s.find("parent")<s.length())
{
sscanf(s.c_str(),"%d is the parent of %d",&t1,&t2);
if(p[t2]==t1) puts("Yes");
else puts("No");
}else if(s.find("left")<s.length())
{
sscanf(s.c_str(),"%d is the left child of %d",&t1,&t2);
if(l[t2]==t1) puts("Yes");
else puts("No");
}else
{
sscanf(s.c_str(),"%d is the right child of %d",&t1,&t2);
if(r[t2]==t1) puts("Yes");
else puts("No");
}
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla