Little Elephant and Tree

题意翻译

# 题目描述 小象对一棵根节点编号为$1$，节点数为$n$的有根树进行$m$次操作。 这棵树每个节点都有一个集合。 第$i$次操作给出$a_i$和$b_i$，把$i$这个数字放入$a_i$和$b_i$这两个点为根的子树里的所有集合中。（包括$a_i$和$b_i$） 在操作完后，输出$c_i$，$c_i$表示有多少个结点（不包括$i$）的集合至少与$i$结点的集合有一个公共数字。 # 输入格式 第一行一个$ n,m(1 \le n,m \le 10^5) $，表示结点数和操作数。 接下来$n-1$行，两个数$u_i$和$v_i$，表示$u_i$到$v_i$有一条边。 接下来$m$行，第$i$行两个数$a_i$和$b_i$表示对这两个点为根节点的子树进行操作。 # 输出格式 输出一行，$n$个数，$c_1,c_2,c_3......c_n$

题目描述

The Little Elephant loves trees very much, he especially loves root trees. He's got a tree consisting of $ n $ nodes (the nodes are numbered from 1 to $ n $ ), with root at node number $ 1 $ . Each node of the tree contains some list of numbers which initially is empty. The Little Elephant wants to apply $ m $ operations. On the $ i $ -th operation $ (1<=i<=m) $ he first adds number $ i $ to lists of all nodes of a subtree with the root in node number $ a_{i} $ , and then he adds number $ i $ to lists of all nodes of the subtree with root in node $ b_{i} $ . After applying all operations the Little Elephant wants to count for each node $ i $ number $ c_{i} $ — the number of integers $ j $ $ (1<=j<=n; j≠i) $ , such that the lists of the $ i $ -th and the $ j $ -th nodes contain at least one common number. Help the Little Elephant, count numbers $ c_{i} $ for him.

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ $ (1<=n,m<=10^{5}) $ — the number of the tree nodes and the number of operations. Each of the following $ n-1 $ lines contains two space-separated integers, $ u_{i} $ and $ v_{i} $ $ (1<=u_{i},v_{i}<=n,u_{i}≠v_{i}) $ , that mean that there is an edge between nodes number $ u_{i} $ and $ v_{i} $ . Each of the following $ m $ lines contains two space-separated integers, $ a_{i} $ and $ b_{i} $ $ (1<=a_{i},b_{i}<=n,a_{i}≠b_{i}) $ , that stand for the indexes of the nodes in the $ i $ -th operation. It is guaranteed that the given graph is an undirected tree.

输出格式

In a single line print $ n $ space-separated integers — $ c_{1},c_{2},...,c_{n} $ .

输入输出样例

输入样例 #1

5 1
1 2
1 3
3 5
3 4
2 3

输出样例 #1

0 3 3 3 3 

输入样例 #2

11 3
1 2
2 3
2 4
1 5
5 6
5 7
5 8
6 9
8 10
8 11
2 9
3 6
2 8

输出样例 #2

0 6 7 6 0 2 0 5 4 5 5 

题意翻译

# 题目描述 小象对一棵根节点编号为$1$，节点数为$n$的有根树进行$m$次操作。 这棵树每个节点都有一个集合。 第$i$次操作给出$a_i$和$b_i$，把$i$这个数字放入$a_i$和$b_i$这两个点为根的子树里的所有集合中。（包括$a_i$和$b_i$） 在操作完后，输出$c_i$，$c_i$表示有多少个结点（不包括$i$）的集合至少与$i$结点的集合有一个公共数字。 # 输入格式 第一行一个$ n,m(1 \le n,m \le 10^5) $，表示结点数和操作数。 接下来$n-1$行，两个数$u_i$和$v_i$，表示$u_i$到$v_i$有一条边。 接下来$m$行，第$i$行两个数$a_i$和$b_i$表示对这两个点为根节点的子树进行操作。 # 输出格式 输出一行，$n$个数，$c_1,c_2,c_3......c_n$