题意:给出一个$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就好啦。
代码不粘了(懒得写了)。