#P9625. Mountainview

    ID: 6242 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2800省选/NOI-树形 DP二分答案按截止时间排序一维前缀和博弈

Mountainview

题目描述

有一棵 nn 个点的树,A 在点 ss,B 希望 A 到达点 tt,而 A 不希望到达点 tt。 游戏开始时,所有边均为干净状态。之后 A 和 B 会进行若干轮博弈,每一轮博弈会按照如下的进程:

  • B 先做决策,B 可以选择:
    1. 不操作
    2. 删去一条边
    3. 打扫一条边
  • A 后做决策,假设当前 A 在点 xx,A 将服从:
    1. 如果与 xx 相邻的所有边都是脏的,则将不会移动。
    2. 如果存在与 xx 相邻的边是干净的,则 A 将任意选择一条干净的边移动(不能不移动),并将这条边变脏。

该轮博弈结束后,若 A 到达了点 tt,则游戏结束,否则进行下一轮博弈。

请求出为使 A 到达点 tt,B 的最小操作次数。注意:是操作次数而非博弈轮数,这意味着若 B 不做操作时将不会对答案产生贡献。假设 A、B 均按照最优策略博弈。

输入格式

第一行三个整数 n,t,sn,t,s。接下来 n−1n-1 行,每行两个整数 x,yx,y 描述树的一条边。

输出格式

输出一行一个整数表示答案。

样例

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

数据范围

子任务 分数 约束条件
subtask1\text{subtask1} 2020 1≤n≤101\le n\le 10
subtask2\text{subtask2} ss 和 tt 在树上相邻
subtask3\text{subtask3} 1≤n≤10001\le n\le 1000
subtask4\text{subtask4} 4040 无特殊限制

对于所有数据:1≤n≤1061\le n\le10^6,1≤s,t≤n1\le s,t\le n。

初始边状态按原样例及站内评测补明。样例若改用所有边初始为脏的规则,最优答案为 22,与原答案 44 不符。