CF979C Kuro and Walking Route(简单的dfs/树形dp)

题意:给出一个$n$个点,$n-1$条边的无向连通图,给出两个点$x,y$,经过$x$后的路径上就不能经过$y$,问可以走的路径$(u,v)$有多少条,($(u,v)$和$(v,u)$考虑为两条不同的路径)。

题目分析:显然这是棵树。。所以从$x$到$y$只有一条简单路径。而且以$x$到$y$的路径上的点为根的话,我们发现不能走的那些点都在$x$,$y$的子树里面。这样的话,统计出$x$子树里的点有$a$个,$y$子树里的点有$b$个,那么整棵树中可以走的路径一共就有$n*(n-1)-a*b$条。

  怎么维护:dfs就好啦。

  代码不粘了(懒得写了)。

上一篇:CDN(内容分发网络)是什么?


下一篇:《LeetBook》leetcode题解(19):Remove Nth Node From End of List[E]——双指针解决链表倒数问题