1142 : Tree Intersection

时间限制Time Limit 2 秒Sec 内存限制Memory Limit 128 兆MB 提交次数Submitted 5 次Times 通过次数Solved 2 次Times

标准评测 Standard

从标准输入读入，结果写到标准输出。评测将输出拆成 token，与标准答案逐项比较，不按整段逐字节比对。 Read from standard input and write to standard output. The judge splits the output into tokens and compares them with the official answer; it does not compare raw bytes.

比对Compare	token 相同即通过。中间的空格、制表符、换行可多可少。Matching tokens pass. Extra spaces, tabs, or newlines between them are ignored.
不同则错Differs	token 个数或内容不同即错误。23 与 2 3、02 与 2、2.0 与 2 均视为不同。A different token count or value is wrong. 23 vs 2 3, 02 vs 2, and 2.0 vs 2 all differ.
输入Input	标准输入，格式见题面。Standard input; format as in the statement.
输出Output	标准输出。Standard output.

模板Template

C++ C Java Python

#include <iostream>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    cout << (a + b) << endl;
    return 0;
}

#include <stdio.h>
int main() {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", a + b);
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int b = in.nextInt();
        System.out.println(a + b);
    }
}

a, b = map(int, input().split())
print(a + b)

题目描述Description

Bobo has a tree with n vertices numbered by 1,2,…,n and (n-1) edges. The i-th vertex has color c_i, and the i-th edge connects vertices a_i and b_i.

Let C(x,y) denotes the set of colors in subtree rooted at vertex x deleting edge (x,y).

Bobo would like to know R_i which is the size of intersection of C(a_i, b_i) and C(b_i, a_i) for all 1 ≤ i ≤ (n − 1). (i.e. |C(a_i, b_i) ∩ C(b_i, a_i)|)

输入格式Input

The input contains at most 15 sets. For each set:

The first line contains an integer n(2 ≤ n ≤ 10⁵).

The second line contains n integers c₁, c₂, …, c_n(1 ≤ c_i ≤ n).

The i-th of the last (n-1) lines contains 2 integers a_i, b_i(1 ≤ a_i, b_i ≤ n).

输出格式Output

For each set, (n-1) integers R₁, R₂, …, R_n − 1.

样例Sample

出题Author

ftiasch

来源Source

湖南省第十二届大学生计算机程序设计竞赛（HNCPC2016）