链接：
https://ac.nowcoder.com/acm/contest/57361/J
来源：牛客网
Students from Antarctic Penguin Language School are counting connected components.
You are given a tree and a cactus with nnn vertices. The vertices is numbered from 111 to nnn.
We define f(i,j)f(i,j)f(i,j) as if we only keep those vertices in the cactus whose number appears on the path from iii to jjj in the tree and the edges between them, how many connected components will be left.
Vertex 111 is the root. For all 1≤x≤n1\leq x\leq n1≤x≤n, you need to calculate:
∑i∈Sx∑j∈Sx,i≤jf(i,j)\sum\limits_{i\in S_x}\sum\limits_{j\in S_x,i \leq j}f(i,j)i∈Sx∑j∈Sx,i≤j∑f(i,j)
in which SxS_xSx means the set of vertices in the subtree of vertex xxx.
A cactus is a simple undirected graph whose nodes are in at most one simple cycle.