AT_nupc2024_f.Labeled Tree Distance

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一棵有 $N$ 个顶点的树 $T$ 。第 $i$ 条边连接顶点 $u_i$ 和 $v_i$ 。最开始时，顶点 $i$ 被涂成颜色 $A_i$ 。接下来给出 $Q$ 个操作，请依次处理每个操作。操作有以下两种类型之一：

1 k x：将顶点 $k$ 涂成颜色 $x$ 。
2 y：输出被颜色 $y$ 涂色的任意两个顶点之间的距离的最大值。

这里，两个顶点 $(u, v)$ 的距离指的是以 $u$ 和 $v$ 为端点的路径上包含的边的数量。

输入格式

输入以如下格式从标准输入读入。

$N$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_{N-1}$ $v_{N-1}$
$A_1\ A_2\ \ldots\ A_N$
$Q$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

其中， $\mathrm{query}_i$ 表示第 $i$ 个查询，格式如下之一：

$1\ k\ x$
$2\ y$

输出格式

设第 2 类查询的次数为 $q$ ，请输出 $q$ 行。对于第 $j\ (1 \le j \le q)$ 行，输出对应于第 $j$ 个第 2 类查询的结果。

输入输出样例

输入#1
```
3
1 2
2 3
1 1 1
3
2 1
1 1 2
2 1
```
输出#1
```
2
1
```

输入#2

输出#2

1
2
1

输入#3

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

输出#3

4
1
2

说明/提示

样例解释 1

最初所有节点都被颜色 $1$ 覆盖，此时颜色 $1$ 覆盖的两个顶点中距离最大的为顶点 $1$ 与顶点 $3$ ，其距离为 $2$ 。之后，如果将顶点 $1$ 改涂为颜色 $2$ ，则此时颜色 $1$ 覆盖的顶点为顶点 $2$ 和顶点 $3$ ，它们之间的距离为 $1$ 。

数据范围

$2 \leq N \leq 10^5$
$1 \leq u_i,v_i \leq N$
$1 \leq A_i \leq N$
$1 \leq Q \leq 10^5$
$1 \leq k \leq N$
$1 \leq x \leq N$
$1 \leq y \leq N$
对于任意一个查询 2 y，颜色 $y$ 至少会覆盖 2 个顶点。
输入均为整数。
输入的图一定是一棵树。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页