hdu 5449 Robot Dog（期望+lca）

本文主要是介绍hdu 5449 Robot Dog（期望+lca），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

hdu 5449 Robot Dog（期望+lca）

题目链接：hdu 5449 Robot Dog

解题思路

n有50000，询问次数有100，每次询问的路径点数最多有100，对于不同询问去做动态规划，开一个$dp[u][i]$表示在第u个节点匹配了i个的期望，显然最坏情况下dp数组的每个状态都要遍历到，复杂度为$o(nqp)$，不能接受。

换个想法，如果我们能知道从节点i走到节点j的期望值$dis[[i][j]$，那么对于每次询问只要按照treasure的位置顺序依次加上相应的期望值即可。不过n很大，预处理每棵树的复杂度为$o(n^2)$，也不能接受。但是$dis[i][j]$的值其实就从节点i到节点j路径上边的期望权值（注意$dis[i][j] ≠ dis[j][i]$）所以，如果我们能分别算出每条边双向移动的代价，剩下的利用树的前缀性质就可以在$log(n)$的复杂度内计算出路径上的期望值。

既以0节点为根，处理出up数组

这篇关于hdu 5449 Robot Dog（期望+lca）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---