磨了几天的QTREE系列,终于基本写完了QTREE1~7的题(其实我刚开始刷的时候还以为只有5题。。。)
So,写(抄)点题解吧~

QTREE1

题目大意

给定一棵n个结点的树,树的边上有权。你被要求支持:
1.修改一条边上的权值。
2.查询两个结点x和y之间的最短路径中经过的最大的边的权值。
其中n<=10^4.

树剖模板题。。。不解释~

QTREE1代码


QTREE2

题目大意

给定一棵n个结点的树,树的边上有权。你被要求支持:
1.查询两个结点x和y之间的最短路径长度。
2.查询从x到y的最短路径的第K条边的长度。
其中n<=10^4.

倍增一下就完了。。

QTREE2代码


QTREE3

题目大意

给定一棵n个结点的树,树的每个结点有黑白两色,初始时所有的结点都是白的。你被要求支持:
1.对一个结点执行反色操作(白变黑,黑变白)
2.查询从1号结点到i号结点的路径上的第一个黑色结点编号。
其中n<=10^5. 查询数目不超过10^5.

可以用树剖,也可以用lct。。

代码?没打~~~


QTREE4

题目大意

给定一棵n个结点的树,树的边上有权,每个结点有黑白两色,初始时所有的结点都是白的。你被要求支持:
1.对一个结点执行反色操作(白变黑,黑变白)
2.查询树中距离最远的两个白点的距离。
其中n<=10^5,查询数目不超过10^5.

这题做法有很多,我用的点分治~
详见这里

QTREE4代码


QTREE5

题目大意

给定一棵n个结点的树,边权均为1。每个结点有黑白两色,初始时所有结点都是黑的。你被要求支持:
1.对一个结点执行反色操作(白变黑,黑变白)
2.查询距离某个特定结点i最远的白点的距离。
其中n<=10^5,查询数目不超过10^5.

跟上一题几乎一样。。。我还是用点分治~~

QTREE5代码


QTREE6

题目大意

给定一棵n个结点的树,每个结点有黑白两色,初始时所有结点都是黑的。你被要求支持:
1.对一个结点执行反色操作(白变黑,黑变白)
2.询问有多少个点与u相连。两个结点u,v相连当且仅当u,v路径上所有点的颜色相同。
其中n<=10^5,查询数目不超过10^5.

这题好神。。膜拜了huzecong的题解后终于明白怎么做了。

解法1是树剖。

对于一个点,维护这个点是黑点的时候,以这个点为根的子树中,有几个点和这个点相连,以及这个点是白点的时候,以这个点为根的子树中,有几个点和它相连。
对于修改,找到深度最浅的同色点的父亲,把当前点的父亲到那个点都减掉当前点的答案,然后改掉当前点的颜色,再找到最浅的同色点的父亲,把当前点的父亲到那个点都加上当前点的答案。
这个复杂度是

QTREE6树剖代码

解法2是lct。

详见QTREE7
复杂度

QTREE6lct代码


QTREE7

题目大意

给定一棵n个结点的树,每个结点有黑白两色和权值。你被要求支持:
1.对一个结点执行反色操作(白变黑,黑变白)
2.询问与u相连的点中点权的最大值。两个结点u,v相连当且仅当u,v路径上所有点的颜色相同。
3.改变一个点的点权。
其中n<=10^5,查询数目不超过10^5.

这题更神。。。让我对lct的理解又加深了。。。
网上貌似只能搜到xiaodao的标程。。于是蒟蒻我就深刻研读了标程,总算明白了怎么做。

这题貌似也是可以用树剖做的,不过我没打。。不过。。嘴巴选手一般都没什么说服力。。。。so,这句话就不要太当真了。。
接下来就只介绍一下lct怎么做。

首先维护两棵树,一棵只有白的点,一棵只有黑的点。对于每个点,用set维护往轻边走的最大值,然后在splay中维护往重边走的最大值。
这个只要在access里面稍加修改就好了:

void access(int rt)
{
    for (int x = 0,y = rt; y; y = p[y]) {
        splay(y);
        if (r[y]) s[y].insert(max[r[y]]);
        if ((r[y] = x)) s[y].erase(s[y].find(max[x]));
        update(x = y);
    }
    splay(rt);
}

注意代码中s[y]的维护。

对于询问只要access之后输出根的答案就好了。对于颜色的修改,把点切掉,然后在另一棵树加上去。对于权值的修改,在两棵树中都改一下就好了。

不过。。。

lct如何把点删掉呢? 说不定可以打一个是否存在的tag~~~

不过有一个更方便的做法:
我们维护边,而不是点。在黑树中,一条树边存在当且仅当深度较深的点是黑的。白的同理。
这样跟一个点连通的点中除了root以外颜色都是一样的。。。然后就很好维护了。。。

复杂度

QTREE7代码

Comments

comments powered by Disqus
Copyright © 2013 lazycal of Shen Ben
Powered by Logdown and Greyshade
Favicon from The Noun Project