CF1413F Roads and Ramen

在火之国，有 $n$ 个村庄和 $n-1$ 条双向道路，任意两个村庄之间都可以通过道路连通。道路只有两种类型：石头路和沙土路。由于火之国经常翻新，每天早上工人们会选择一条道路并翻转其类型（如果原来是沙土路就变成石头路，反之亦然）。此外，这里的人都很喜欢拉面，因此每天早上每条石头路的中间都会设立一个拉面亭，到了晚上所有拉面亭都会被移除。 在接下来的 $m$ 天中，每天又有一条道路被翻转后，Naruto 和 Jiraiya 会选择一条简单路径——即从某个村庄出发，到达另一个（也可能是同一个）村庄，且路径上每条道路最多经过一次。由于他们都非常喜欢拉面，他们会在每条石头路上买一杯拉面，并由其中一人吃掉。为了公平起见，他们只会选择能让两人吃到相同数量拉面的路径。由于他们也喜欢旅行，他们会选择任意一条最长的路径。每次翻新后，请你输出他们能选择的最长合法路径的长度（即路径上道路的数量）。

第一行包含一个正整数 $n$（$2 \leq n \leq 500\,000$），表示火之国的村庄数量。 接下来的 $n-1$ 行，每行包含三个正整数 $u$、$v$ 和 $t$（$1 \leq u, v \leq n$，$t \in \{0,1\}$），表示一条连接村庄 $u$ 和 $v$ 的道路，$t$ 表示道路的初始类型：$0$ 表示沙土路，$1$ 表示石头路。道路按照输入顺序编号为 $1$ 到 $n-1$。 接下来一行包含一个正整数 $m$（$1 \leq m \leq 500\,000$），表示 Naruto 和 Jiraiya 旅行的天数。 接下来的 $m$ 行，每行包含一个正整数 $id$（$1 \leq id \leq n-1$），表示当天早上被翻转类型的道路编号。 保证任意两个村庄之间都存在道路连通。

输出 $m$ 行，第 $i$ 行输出第 $i$ 天他们能选择的最长合法路径的长度。

在第 $3$ 条道路翻新后，最长路径包含道路 $1$、$2$ 和 $4$。 在第 $4$ 条道路翻新后，最长路径包含道路 $1$ 和 $2$。 在第 $1$ 条道路翻新后，最长路径包含道路 $1$、$2$ 和 $3$。 在第 $3$ 条道路翻新后，最长路径包含道路 $1$、$2$ 和 $4$。 在第 $4$ 条道路翻新后，最长路径包含道路 $2$ 和 $4$。 由 ChatGPT 4.1 翻译