A6153. 「USACO 2023 US Open Platinum」Triples of Cows
编程题
NOI/NOI+/CTSC
知识点
题目描述
**题目译自 [USACO 2023 US Open Contest, Platinum](http://usaco.org/index.php?page=open23results) Problem 3. [Triples of Cows](http://usaco.org/index.php?page=viewproblem2&cpid=1334)**
最初 FJ 有 $N\ (2\le N\le 2\cdot 10^5)$ 头奶牛，这些奶牛的编号为 $1\ldots N$，这些奶牛中有 $N-1$ 对朋友，朋友关系形成了一棵树。这些奶牛会一个接一个离开农场去度假。在第 $i$ 天，奶牛 $i$ 会离开农场，然后奶牛 $i$ 的朋友中目前还在农场的那些会两两结为朋友。
对于 $1$ 到 $N$ 的每个 $i$，就在奶牛 $i$ 离开之前，有多少个不同奶牛的有序三元组 $(a,b,c)$ 满足 $a,b,c$ 三头奶牛都没去度假，且 $a$ 和 $b$ 是朋友，$b$ 和 $c$ 是朋友？
最初 FJ 有 $N\ (2\le N\le 2\cdot 10^5)$ 头奶牛，这些奶牛的编号为 $1\ldots N$，这些奶牛中有 $N-1$ 对朋友，朋友关系形成了一棵树。这些奶牛会一个接一个离开农场去度假。在第 $i$ 天，奶牛 $i$ 会离开农场，然后奶牛 $i$ 的朋友中目前还在农场的那些会两两结为朋友。
对于 $1$ 到 $N$ 的每个 $i$，就在奶牛 $i$ 离开之前，有多少个不同奶牛的有序三元组 $(a,b,c)$ 满足 $a,b,c$ 三头奶牛都没去度假，且 $a$ 和 $b$ 是朋友，$b$ 和 $c$ 是朋友？
输入格式
第一行一个整数 $N$。
接下来 $N-1$ 行，每行两个整数 $u_i$ 和 $v_i\ (1\le u_i,v_i\le N)$，表示最初奶牛 $u_i$ 和奶牛 $v_i$ 是朋友。
接下来 $N-1$ 行，每行两个整数 $u_i$ 和 $v_i\ (1\le u_i,v_i\le N)$，表示最初奶牛 $u_i$ 和奶牛 $v_i$ 是朋友。
输出格式
输出 $N$ 行，第 $i$ 行输出对于第 $i$ 天的答案。
输入输出样例
输入 #1
3 1 2 2 3
输出 #1
2 0 0
输入 #2
4 1 2 1 3 1 4
输出 #2
6 6 0 0
输入 #3
5 3 5 5 1 1 4 1 2
输出 #3
8 10 2 0 0
说明/提示
- 4-5 组数据：$N\le 500$
- 6-10 组数据：$N\le 5000$
- 11-20 组数据：无附加限制
- 6-10 组数据：$N\le 5000$
- 11-20 组数据：无附加限制