P8674 - LTCS - ZUFEOJ

内存限制：128 MB 时间限制：1 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：3 通过：1

Tcs has just learned the subsequence of a sequence. Now Tcs wants to define the subsequence of a rooted tree. A rooted tree

T_a

which satisfies the following constraints is called a subsequence of another rooted tree

T_b

Suppose that there are $N$ vertices in $T_a$ numbered as $1,2,…,N1,2,\ldots,N$ and there are $M$ vertices in $T_b$ numbered as $1,2,…,M1,2,\ldots,M$ . There is a function $F:{1,2,…,N}→{1,2,…,M}F:\{1,2,\ldots,N\} \to \{1,2,\ldots,M\}$ , which satisfies $∀x,y∈{1,2,…,N},x≠y⇒F(x)≠F(y)\forall x, y \in \{1,2,\ldots,N\}, x \ne y \Rightarrow F(x) \not = F(y)$ .
For all vertices $u$ in $T_a$ , $c_{a, u} = c_{b, F(u)}$ holds, where $c_{i, u}$ is the value of vertex $u$ in $T_i$ .
If vertex $u$ is an ancestor of vertex $v$ in $T_a$ , then vertex $F (u)$ is an ancestor of vertex $F (v)$ in $T_b$ .
For distinct vertices $u, v, w$ in $T_a$ , if vertex $u$ is the father of both vertex $v$ and vertex $w$ , then vertex $F (u)$ is on the simple path between vertex $F (v)$ and vertex $F (w)$ in $T_b$ .

A rooted tree

T_3

is called a TCS (Tree Common Subsequence) of

T_1

and

T_2

when

T_3

is a subsequence of both rooted trees

T_1

and

T_2

. Given the rooted trees

T_1

and

T_2

whose roots are both vertex

1

, Tcs wants to find the largest size of the TCS of

T_1

and

T_2

The first line contains two integers  $n, m$  ( $2≤n,m≤5002\leq n, m\leq 500$ ) — the number of vertices in  $T_1$  and  $T_2$ , respectively.
The second line contains  $n$  integers  $c1,1,c1,2,…,c1,nc_{1, 1}, c_{1, 2}, \dots, c_{1, n}$  ( $\le c_{1, i} \le 500$ ) — the value of each vertex in  $T_1$ .
The third line contains  $m$  integers  $c2,1,c2,2,…,c2,mc_{2, 1}, c_{2, 2}, \dots, c_{2, m}$  ( $\le c_{2, i} \le 500$ ) — the value of each vertex in  $T_2$ .
Each of the next  $n - 1$  lines contains two integers  $u$  and  $v$  ( $\le u, v \le n$ ) — an edge connecting vertices  $u$  and  $v$  in  $T_1$ . 
Each of the next  $m - 1$  lines contains two integers  $u$  and  $v$  ( $\le u, v \le m$ ) — an edge connecting vertices  $u$  and  $v$  in  $T_2$ .

Print an integer in a single line, denoting the largest size of the TCS of

2022 牛客1

8674: LTCS

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签