[蓝桥杯 2014 国 C] 套娃

Luogu

IDLGP8616

Time1000ms

Memory128MB

DifficultyP5

2014蓝桥杯国赛

作为 drd 送的生日礼物，atm 最近得到了一个俄罗斯娃娃。他对这个俄罗斯娃娃的构造很感兴趣。俄罗斯娃娃是一层一层套起来的。假设：一个大小为 $x$ 的俄罗斯娃娃里面可能会放任意多个大小小于 $x$ 的俄罗斯娃娃（而市场上的套娃一般大娃里只能放一个小娃）。 drd 告诉 atm，这个俄罗斯娃娃是由 $n$ 个小娃娃组成的，它们的大小各不相同。我们把这些小娃娃的大小从小到大依次记为 $1$ 到 $n$。如果 atm 想观赏大小为 $k$ 的小娃娃，他会先看这个小娃娃是否已经在桌子上了。如果已经在桌子上，那么他就可以观赏了。否则他就打开桌子上某一个俄罗斯娃娃，将它套住的所有的小娃娃拿出来，摆在桌子上。一开始桌子上只有 drd 送的大小为 $n$ 的娃娃。注意，他只会将其中所有小娃娃拿出来，如果小娃娃里面还套着另外的小娃娃，他是不会将这些更里层的这些小娃娃拿出来的。而且 atm 天生具有最优化的强迫症。他会最小化他所需要打开的娃娃的数目。 atm 是一个怪人。有时候他只想知道观看大小为 $x$ 的娃娃时需要打开多少个娃娃（但并不去打开）；有时候听 drd 说某个娃娃特别漂亮，于是他会打开看。现在请你输出他每次需要打开多少个娃娃。 ## Input 第一行两个数 $n,m$，表示娃娃的数目以及 atm 想看的娃娃的数目。接下来 $n-1$ 行，每行两个数 $u,v$，表示大小为 $u$ 的娃娃里面套着一个大小为 $v$ 的娃娃。保证 $u>v$。接下来 $m$ 行，每行形如： - `P x`：表示 atm 一定要看到大小为 $x$ 的娃娃（这会打开 $x$ 且打开的 $x$ 不计入答案总数）； - `Q x`：表示 atm 只想知道为了看大小为 $x$ 的娃娃，他需要打开多少个娃娃，但实际上并不打开他们。 ## Output 输出 $m$ 行。对应输入中 $P$ 操作或 $Q$ 操作需要打开（或假想打开）多少个俄罗斯娃娃。 [samples] ## Note 对于 $30\%$ 的数据：$n,m \le 1000$。对于 $100\%$ 的数据：$n,m \le 100000$。

Samples

Input #1

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[蓝桥杯 2014 国 C] 套娃",
    "description": {
      "content": "作为 drd 送的生日礼物，atm 最近得到了一个俄罗斯娃娃。他对这个俄罗斯娃娃的构造很感兴趣。 俄罗斯娃娃是一层一层套起来的。假设：一个大小为 $x$ 的俄罗斯娃娃里面可能会放任意多个大小小于 $x$ 的俄罗斯娃娃（而市场上的套娃一般大娃里只能放一个小娃）。 drd 告诉 atm，这个俄罗斯娃娃是由 $n$ 个小娃娃组成的，它们的大小各不相同。我们把这些小娃娃的大小从小到大依次记为 $1$ ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP8616"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "作为 drd 送的生日礼物，atm 最近得到了一个俄罗斯娃娃。他对这个俄罗斯娃娃的构造很感兴趣。\n\n俄罗斯娃娃是一层一层套起来的。假设：一个大小为 $x$ 的俄罗斯娃娃里面可能会放任意多个大小小于 $x$ 的俄罗斯娃娃（而市场上的套娃一般大娃里只能放一个小娃）。\n\ndrd 告诉 atm，这个俄罗斯娃娃是由 $n$ 个小娃娃组成的，它们的大小各不相同。我们把这些小娃娃的大小从小到大依次记为 $1$ ...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments