记一次突击检测

Typora的稳定性令人堪忧啊——把我刚写好的blog给吞了……wqnmlgb

假装重新写一次

今天本来是比较平淡的一天，甚至还有些烦闷——毕竟快期末考了，各种试卷和作业，我也就呵呵了

晚上还是在机房，结果创新班的同学们都没来，我怕不是要被班主任D死了

本来想一个人静静地学一些算法和姿势的，但是心始终静不下来，开黑打比赛的学弟们太吵了，一群嘤嘤怪

于是就想起来走走，换换脑子，然后就被学弟们拉去想题了……

题目大意：给出一棵 n $n$个节点的树，每条边有一个需要走的次数 need $need$， m $m$次询问，每次给出一对点 s $s$和 t $t$，问从 s $s$走到 t $t$的最小代价。 n,m≤2×105 $n,m\le 2\times {10}^5$

什么鬼啊，拿到题目就懵逼了……不行啦，你们的学长太菜啦…… O(n×m) $O(n\times m)$的不是很好嘛……

等会，我好像有个不成熟的想法，树剖怎样？

初始化所有边走偶数次，考虑把 s $s$到 t $t$的路径上变成奇数次，那么分类讨论一下，发现对原树的边权正负标号一下直接树剖， O(m×log22n) $O(m\times {\log }_2^{2}n)$的时间复杂度好像很正确啊……

事实上，这就是正解

第一次觉得自己还是很有希望的嘛，只是自己的努力程度还是不够吧

果然学算法、刷题的脚步不能停下，必须提高效率，加紧前进的速度

等文化课的所有事情结束，我会回来，重新站在这儿