[CCC 2022 S5] Good Influencers

Luogu

IDLGP8399

Time1000ms

Memory128MB

DifficultyP5

2022CCC（加拿大）

给定一棵**树**，点 $i$ 的点权是 $c_i$，上面有的点是蓝点 `Y` ，有的点是白点 `N` 。每次操作可以选定一个**蓝**点，将和这个蓝点直接相连的白点染成蓝色，代价是选定的蓝点的点权。求将整个树染成蓝色的最小代价。数据保证存在至少一个白点和至少一个蓝点。 ## Input 第一行一个整数 $n$ 表示树的大小。接下来 $n-1$ 行每行两个整数 $a_i$,$b_i$，表示 $a_i$ 和 $b_i$ 直接相连。接下来一行 $n$ 个字符表示每个点初始颜色。接下来一行 $n$ 个整数表示每个点的点权。 ## Output 一行，表示最小花费。 [samples] ## Note 对于 $30\%$ 的数据：$2\le n\le 2000,1\le c_i\le1000$，且 $a_i=i,b_i=i+1$ 。对于另外 $50\%$ 的数据：$2\le n\le 2000,1\le c_i\le1000$ 。对于 $100\%$ 的数据：$2\le n\le 2\times10^5,1\le c_i\le1000$。

Samples

Input #1

Output #1

Input #2

15
1 5
5 2
2 15
15 4
2 10
8 3
3 1
1 6
11 6
12 6
11 9
11 14
12 7
13 7
NNYYYNYYNNNNNNN
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[CCC 2022 S5] Good Influencers",
    "description": {
      "content": "给定一棵**树**，点 $i$ 的点权是 $c_i$，上面有的点是蓝点 `Y` ，有的点是白点 `N` 。每次操作可以选定一个**蓝**点，将和这个蓝点直接相连的白点染成蓝色，代价是选定的蓝点的点权。 求将整个树染成蓝色的最小代价。 数据保证存在至少一个白点和至少一个蓝点。 ",
      "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": "LGP8399"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一棵**树**，点 $i$ 的点权是 $c_i$，上面有的点是蓝点 `Y` ，有的点是白点 `N` 。每次操作可以选定一个**蓝**点，将和这个蓝点直接相连的白点染成蓝色，代价是选定的蓝点的点权。\n\n求将整个树染成蓝色的最小代价。\n\n数据保证存在至少一个白点和至少一个蓝点。\n\n## Input\n\n第一行一个整数 $n$ 表示树的大小。\n\n接下来 $n-1$ 行每行两个整数 $a_i$,$b_i...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments