欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【百度之星2014~复赛)解题报告】The Query on the Tree

程序员文章站 2022-07-10 09:18:20
...

声明

   笔者最近意外的发现 笔者的个人网站 http://tiankonguse.com/ 的很多文章被其它网站转载,但是转载时未声明文章来源或参考自 http://tiankonguse.com/ 网站,因此,笔者添加此条声明。

    郑重声明:这篇记录《 【百度之星2014~复赛)解题报告】The Query on the Tree》转载自 http://tiankonguse.com/ 的这条记录:http://tiankonguse.com/record/record.php?id=673

 

前言

这几天把毕业答辩的事弄完了,于是买票出来玩,结果周六是百度之星的复赛,于是我就没有办法来做比赛了,不过看了看题,目测可以过我两三道题.

今天已经是比赛的第二天了,我还一直没有时间来A掉这些题,今晚抽空先把最简单的线段树那道题A了再说.

 

正文

题意

题目说的很清楚了,自己看吧.

 

有一棵树,树的每个点有点权,每次有三种操作:
  1. Query x 表示查询以x为根的子树的权值和。
  2. Change x y 表示把x点的权值改为y(0<=y<=100)。
  3. Root x 表示把x变为根。

分析

 

这道题的数据起始很弱的.

我最初的想法就可以把这道题过掉.

 

最初的想法

 

首先对这个树按1为根dfs根优先编号,这个应该没有什么疑问.

编号的好处是一个子树变为了一个连续的区间.

编号的时候保存一下这个子树的编号区间,保存在子树的根上.

编号的时候顺便计算一下子树的权值和.

编号的时候记录一下一个节点的父节点.

 

修改操作

 

先说说修改操作,修改某个节点时,就算出这个节点应该增加多少,然后从这个节点开始更新,一直更新到根1.

平均复杂度 O( log(n) )

最坏复杂度 O( n )

 

设置根

 

这里我们需要一个变量来表示目前的根是那个节点,比如使用root变量,默认值是1.

设置根只需要把根变量更新一下即可.

平均复杂度 O( 1 )

最坏复杂度 O( 1 )

 

查询操作

查询的时候分三种情况:

1.查询的节点是目前的根 

这个时候答案显然是整个树的权值和,返回 根1的权值和即可.

 

2.目前的根不是查询的节点的某个子孙(即根不在查询的子树里面)

这个时候,答案和根是1的情况相同,及直接返回查询节点的权值和即可.

怎么判断根是不是查询节点的子孙呢?

平常的方法是用 LCA 查询,这里我直接使用子树区间来判断即可.

 

3.目前的根是查询节点的某个子孙.

这个时候,我们想象一下,我们拿起根,查询节点的子孙有那些呢?

即那些会在查询节点的下面呢?

假设查询节点是 x,  x的一个儿子是y, 根是y的一个子孙(也可能是y).

这个时候,我们拿起根,x 应该变成 y 的儿子了吧.

这时树的权值应该是 x 原先的权值和 - y 节点的权值和 + 不在x子树区间的全职和.

然后,我们可以发现 x 原先的权值和 + 不在x子树区间的权值和 = 整个树的权值和.

故最终答案是 整个树的权值和 - y节点的权值和.

 

问题:怎么找到y节点.

有两个方法:

1.枚举x的儿子来判断

2.从根不断的找父亲来判断.

由于题意没有说最多儿子有多少个,所以第一个方法最坏情况下为 O( n ) (很多儿子)

对应的,第二个方法最坏情况下也是 O( n ) (树退化为链表).

 

不过我们不用管最坏情况,先这样实现了再说.

 

综合操作复杂度log(n)

 

线段数优化

首先对于修改操作,线段树优化后可以使最坏情况达到 O( log( n ) ).

对于查询操作,由于需要知道 x 的那个儿子 y, 这个我目前没有想到 O( log( n ) ) 的方法.

学弟说那只能使用二分了.

但是怎么二分呢?

发现二分不了,不过可以使用随机算法来优化找儿子的效率.

起初我们是遍历x的所有儿子,这里我们随机挑一个儿子来寻找.这也算是一个比较好的优化方法吧.

 

 

代码

暴力版代码 https://github.com/tiankonguse/ACM/blob/master/astar/2014/3/2.2.cpp(比较简洁)

线段树优化版代码 https://github.com/tiankonguse/ACM/blob/master/astar/2014/3/2.cpp

对于上面说的几个方法我只实现了两个,其他的都很简单,有兴趣的朋友可以尝试一下.

 

参考

http://blog.csdn.net/hongrock/article/details/27839237(这个参考主要用于确认暴力不会超时,如果精心构造数据,这个方法会超时的)