[yLCPC2024] F. PANDORA PARADOXXX

Luogu
IDLGP10238
Time1000ms
Memory512MB
DifficultyP5
洛谷原创最近公共祖先 LCA洛谷月赛离线处理
给定一棵 $n$ 个结点的树。一棵树被定义为一个有 $n$ 个点和 $n-1$ 条边的无向连通图。这棵树的边有边权。两点 $u,v$ 间的距离 $\mathrm{dist}(u,v)$ 定义为从 $u$ 到 $v$ 的简单路径边权和。可以证明树上两点间的简单路径是唯一的。特别的,我们规定 $\mathrm{dist}(u, u) = 0$。 现在有 $q$ 次操作,每次会删除这棵树上的一条边。显然在做出至少一次操作后,这棵树会被分成若干个连通块。你需要在每次操作后都求出每个连通块内距离最远的两个点的距离的最大值。 形式化的,每次操作后,你要求出 $$\max\limits_{c \in C}\{\max\limits_{u, v \in c} \mathrm{dist}(u,v)\}$$ 其中 $C$ 表示当前所有连通块构成的集合。 ## Input **本题单个测试点内有多组测试数据**。第一行是一个正整数 $T$,表示数据组数。对每组数据: 输入第一行是两个整数 $n, q$($1 \leq q < n \leq 10^5$),依次表示树的结点数和操作数。 接下来 $n - 1$ 行,每行三个整数 $u,v,w$($1 \leq u, v \leq n$,$1 \leq w \leq 10^5$)表示树上有一条连接 $u$ 和 $v$ 的权值为 $w$ 的边。 接下来 $q$ 行,每行一个整数 $e_i$($1 \leq e_i < n$),表示这次操作删除了输入的第 $e_i$ 条边。数据保证每条边只会被删除一次。 数据保证单个测试点内的 $n$ 之和不超过 $3 \times 10^5$。 ## Output 对每组数据,输出 $q$ 行,每行一个整数,依次表示每次操作后所求的答案。 [samples] ## Background 扶苏所在的城市的机厅联合举办了 KING of PerforPandora! 但是因为大雪封路,有些机厅不能到达。她想知道在能互相到达的机厅中距离最远为多少。 ## Note #### 提示 请注意大量的数据读入和输出对程序效率造成的影响,选择合适的读入输出方式,不要频繁刷新输出缓冲区,避免超时。
Samples
Input #1
2
4 2
1 2 1
2 3 2
3 4 3
2
3
12 2
1 2 1
2 3 1
1 4 3
2 5 4
5 6 3
5 7 2
7 8 1
8 9 1
9 10 1
7 11 5
8 12 3
4
6
Output #1
3
1
10
9
API Response (JSON)
{
  "problem": {
    "name": "[yLCPC2024] F. PANDORA PARADOXXX",
    "description": {
      "content": "给定一棵 $n$ 个结点的树。一棵树被定义为一个有 $n$ 个点和 $n-1$ 条边的无向连通图。这棵树的边有边权。两点 $u,v$ 间的距离 $\\mathrm{dist}(u,v)$ 定义为从 $u$ 到 $v$ 的简单路径边权和。可以证明树上两点间的简单路径是唯一的。特别的,我们规定 $\\mathrm{dist}(u, u) = 0$。 现在有 $q$ 次操作,每次会删除这棵树上的一条边。显",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10238"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一棵 $n$ 个结点的树。一棵树被定义为一个有 $n$ 个点和 $n-1$ 条边的无向连通图。这棵树的边有边权。两点 $u,v$ 间的距离 $\\mathrm{dist}(u,v)$ 定义为从 $u$ 到 $v$ 的简单路径边权和。可以证明树上两点间的简单路径是唯一的。特别的,我们规定 $\\mathrm{dist}(u, u) = 0$。\n\n现在有 $q$ 次操作,每次会删除这棵树上的一条边。显...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments