题目大意children trips题解.pdfVIP

Solution

题目大意：

给定一棵树，边权为1或2。每次给定点u和点，并给出距离。vd

一开始在点u，每天从当前点出发向点走不大于的距离到达一个点，vd

uv

询问从点走到点至少需要多少天？

关键字：分块，分类讨论

解法：

第一类：对于dn的询问。

uvulcavlca

到的路径分为两段：从到和从到。易证，方向

ulcau

相答案并没有太大影响。对于每段路（以到为例），我们从

lcalcau′

一天一天往上走走到最接近的点，还没到，记该点为，同理

′′′′′

vuu+vv+uv

得出点。那么该询问的答案为到的天数到的天数到

的天数。

′

ulcauv

问题是如何求出到的天数，并求出（同理）。

我们采用离线处理，将每个询问分出来的两段路径x到（是x

yy

的祖先）记在点处。对这棵树进行dfs（根随便）。记xdisi[]为点到根i

的距离，当到达一个点node时，我们可以轻易这样的一个数组

node

，，那么往上走一天所到

Find[]Findi[]=j|dis[j]=min{disk[]|disk[]≥i}

达的点就是Finddisnode[[]−d]。那么对于询问到的答案只需xy一

天一天往上走即可。

第二类：对于d≤n的询问。

uvulcav

总体思路与第一类相同，我们同样将和的路径分为到和

lca

到两段。

ulcau′

当处理到的天数和求出时，我们可以每次处理n天，当走

lca

n天超过了，再一天一天往上走。

至于在距离为d时一个点向根的方向走1天，走n天能到达

哪个点，借助距离为d−1时的结果能够轻易完成这个任务。

时间复杂度：On(*n)