TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5951
  • 题目
  • P5951「JOI 2019 Final」独特的城市
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 2s,256m
    问题描述

    为防止卡OJ行为,本题只放了部分官方数据。完整评测所有数据请前往LiberOJ的这道题

    译自 JOI 2019 Final T5「珍しい都市 / Unique Cities

    JOI 国有 \(N\) 个城市,城市从 $1$ 到 \(N\) 编号。这些城市被 \(N-1\) 条双向道路连接,第 \(i\) 条路连接两个城市 \(A_i\)\(B_i\)。从任何城市出发,可以到达所有城市。

    JOI 国有些特产,每种特产的编号都在 $1$ 到 \(M\) 之间(包括 $1$ 和 \(M\)),但是 $1$ 到 \(M\) 的某些整数可能不代表 JOI 国的特产。JOI 国的每个城市都产一种特产。\(j\) 城产的特产是 \(C_j\)。多个城市可能产相同的特产。

    我们定义两个城市之间的距离为从一个城市到另一个城市需要经过的最少道路数,对于城市 \(x\ (1\le x\le N)\),我们定义城市 \(y\ (1\le y\le N,y\neq x)\)独特的城市当且仅当对于任何一个城市 \(z\ (1\le z\le N,z\neq x,z\neq y)\)\(x\)\(y\) 间的距离不等于 \(x\)\(z\) 之间的距离。

    JOI 国交通部部长 K 先生想知道对于城市 \(j\ (1\le j\le N)\)独特的城市一共能产多少种特产。

    给出 JOI 国的道路信息与每个城市产的特产,写一个程序计算对于每个城市的独特的城市,一共能产多少种特产。

    输入格式

    第一行两个整数 \(N,M\),意义如题目描述。

    接下来 \(N-1\) 行,每行两个整数 \(A_i,B_i\),意义如题目描述。

    最后一行 \(N\) 个正整数,第 \(j\) 个为 \(C_j\),意义如题目描述。

    输出格式

    输出 \(N\) 行,第 \(j\ (1\le j\le N)\) 行表示对于城市 \(j\ (1\le j\le N)\)独特的城市一共能产多少种特产。

    提示

    样例输入 1

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

    样例输出 1

    2
    0
    1
    1
    1
    

    样例说明 1

    对于城市 $1$,它的独特城市是城市 $2,3$,城市 $2$ 产特产 $2$,城市 $3$ 产特产 $1$,一共产两种特产,因此答案是 $2$;
    对于城市 $2$,没有独特城市,因此输出 $0$;
    对于城市 $3$,它的独特城市是城市 $1$,城市 $1$ 产特产 $1$,因此答案是 $1$;
    对于城市 $4$,它的独特城市是城市 $1,3$,城市 $1$ 产特产 $1$,城市 $3$ 产特产 $1$,一共产一种特产,因此答案是 $1$;
    对于城市 $5$,它的独特城市是城市 $1,3$,城市 $1$ 产特产 $1$,城市 $3$ 产特产 $1$,一共产一种特产,因此答案是 $1$;

    注意,没有编号为 $3$ 的特产。

    样例输入 2

    7 1
    1 2
    2 3
    3 4
    4 5
    5 6
    6 7
    1 1 1 1 1 1 1
    

    样例输出 2

    1
    1
    1
    0
    1
    1
    1
    

    样例说明 2

    本组样例符合子任务 $2$ 的限制。

    样例输入 3

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

    样例输出 3

    4
    3
    4
    2
    0
    2
    2
    0
    3
    2
    

    样例说明 3

    本组样例符合子任务 $3$ 的限制。

    样例输入 4

    22 12
    9 6
    12 13
    4 20
    21 22
    3 19
    2 9
    6 18
    18 11
    18 3
    16 2
    6 4
    3 17
    16 10
    8 16
    22 1
    16 14
    15 8
    9 21
    2 12
    21 5
    12 7
    1 1 4 8 4 11 7 6 7 11 6 11 10 4 7 5 3 12 9 6 12 2
    

    样例输出 4

    2
    0
    1
    1
    1
    1
    1
    0
    0
    1
    2
    0
    1
    1
    2
    0
    2
    1
    2
    3
    0
    0
    

    对于全部数据,$1\le N\le 2\times 10^5,1\le M\le N,1\le A_i,B_i\le N\ (A_i\neq B_i,1\le i\le N-1),1\le C_j\le M\ (1\le j\le M)$,并且保证从一个城市永远可以通过道路到达任何一个城市。

    详细子任务及附加限制如下表:

    Subtask 附加限制 分值
    1 \(N\le 2000\) 4
    2 \(M=1\) 32
    3 \(M=N,C_j=j\ (1\le j\le N)\)  32 
    4 32

    点此下载大样例