题解 洛谷P5018【对称二叉树】(noip2018T4)
2024-09-03 19:04:32
\(noip2018\) \(T4\)题解
其实呢,我是觉得这题比\(T3\)水到不知道哪里去了
毕竟我比较菜,不大会\(dp\)
好了开始讲正事
这题其实考察的其实就是选手对D(大)F(法)S(师)的掌握程度
考完试有人说这题是马拉车,吓死我了
首先,你把数据读入之后,先用一个大法师把以每个节点为根的子树的大小和权值都预处理出来,方便待会剪枝
然后,你对以每个节点为根的子树,都判断一下以下条件(这时刚才处理的东西就有用了)
① 左子树和右子树的节点数是否相等
② 左子树和右子树的权值是否相等
③ 以当前节点为根的子树大小是不是超过答案
第三个很重要,不加(洛谷数据)最后一个点会TLE
有一个显而易见的剪枝:因为答案至少是1,所以大小为1的子树就不用check了,不然浪费常数
然后就是暴力判了
递归下去,建立两个队列,保存当前处理到的左子树上和右子树上的节点,判左子树当前节点的左儿子和右子树当前节点的右儿子权值是否相等,右子树当前节点的左儿子和左子树当前节点的右儿子权值是否相等(注意对应)
还有判下对应的节点有没有一个是空的一个没空的情况
如果不相等就返回
相等的话就扔进队列(注意对应顺序!)
注意:上述处理一定要左右子树一起做,不能先处理一边,再处理另一边,不然会WA
到最后如果都可以的话就return true
附考场代码
不得不说,为了能过,我加了一堆卡常
3e6的输入规模应该还是要快读的吧
# include <bits/stdc++.h>
# define R register
const int MaxN = 1000010;
struct node//节点
{
int val;
int l, r;
};
node a[MaxN];
int f[MaxN], val[MaxN], ind[MaxN];//f[i]表示以i为根的子树大小,val表示以i为根的子树权值和,ind没啥用
inline void read(int &x)//快读
{
x = 0;
bool op = 1;
char ch = getchar();
while(ch > '9' || ch < '0')
{
if(ch == '-')
op = 0;
ch = getchar();
}
while(ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch - '0'), ch = getchar();
if(!op)
x = -x;
}
void dfs(int root)
{
if(root == -1)
return;
if(a[root].l == -1 && a[root].r == -1)
f[root] = 1, val[root] = a[root].val;
else
{
dfs(a[root].l);
dfs(a[root].r);
f[root] = f[a[root].l] + f[a[root].r] + 1;
val[root] = val[a[root].l] + val[a[root].r] + a[root].val;
}
}
inline int check(int x)
{
std::queue<int> l, r;
l.push(x), r.push(x);
while(!l.empty() || !r.empty())
{
if(l.empty() || r.empty())
return false;//一边空了,一边没空
R int lx = l.front(), rx = r.front();
l.pop(), r.pop();
if(a[lx].val != a[rx].val)
return false;
R int lson[3], rson[3];
lson[1] = a[lx].l, lson[2] = a[lx].r;//左子树当前节点的左儿子,左子树当前节点的右儿子
rson[1] = a[rx].l, rson[2] = a[rx].r;//右子树当前节点的左儿子,右子树当前节点的右儿子
if((lson[1] == -1 && rson[2] != -1) || (lson[1] != -1 && rson[2] == -1))
return false;//一边空了,一边没空
if((lson[2] == -1 && rson[1] != -1) || (lson[2] != -1 && rson[1] == -1))
return false;//一边空了,一边没空
if(lson[1] != -1)
l.push(lson[1]);
if(lson[2] != -1)
l.push(lson[2]);
if(rson[2] != -1)
r.push(rson[2]);
if(rson[1] != -1)
r.push(rson[1]);
//推进队列
}
return true;
}
int main()
{
// freopen("tree.in", "r", stdin);
// freopen("tree.out", "w", stdout);
R int n;
scanf("%d", &n);
for(R unsigned i = 1; i <= n; ++i)
read(a[i].val);
for(R unsigned i = 1; i <= n; ++i)
read(a[i].l), read(a[i].r), ++ind[a[i].l], ++ind[a[i].r];//处理入度
R unsigned root;
for(R unsigned i = 1; i <= n; ++i)
{
if(!ind[i])
{
root = i;
break;
}
}//找树根
dfs(root);//预处理
int ans = 1;
for(R unsigned i = 1; i <= n; ++i)//枚举子树
{
if(f[a[i].l] != f[a[i].r])
continue;//剪枝1
if(val[a[i].l] != val[a[i].r])
continue;//剪枝2
if(f[i] < ans || f[i] == 1)
continue;//剪枝3
if(check(i))
ans = f[i];//更新答案
}
printf("%d", ans);
fclose(stdin);
fclose(stdout);
return 0;
}
最新文章
- EFUpdate
- A Beginner&#39;s Guide to Paxos
- rgba()兼容IE8
- Psp个人软件开发软件需求分析和用例分析
- 创建 Transact-SQL 作业步骤
- python中时间格式
- 组合数学:容斥原理(HDU1976)
- Mysql启动失败 MYSQL:The server quit without updating PID file
- nginx-configure执行大致流程
- windows 7 memcached报failed to install service or service already installed的解决方案
- 使用Nginx+CppCMS构建高效Web应用服务器
- [BZOJ2743] [HEOI2012] 采花 (树状数组)
- Java异常处理-----java异常体系
- pyqt5安装问题
- AGC 030D.Inversion Sum(DP 期望)
- c#npoi 报错Cannot get a numeric value from a text cell 的解决
- [daily][dpdk] 内核模块(网卡驱动)无法卸载
- 根据模板导出Excel报表并复制模板生成多个Sheet页
- 聊聊javascript的null和undefined
- Oracle 12cR1中性能优化新特性之全数据库缓冲模式