染色 (color)
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
[丛雨]设计了一棵 个点的有根树,节点编号为 ,根节点为 。最开始所有点都是白色,你需要选择一些点染成黑色,同时有若干条限制,限制有两种: 类限制: 的子树内至少有 个点被染成黑色。 类限制: 的子树外至少有 个点被染成黑色。 请问最少把多少个点染成黑色才能满足条件,如果无解输出 。
输入格式(color.in)
第一行一个正整数 。 接下来 行,每行两个正整数 ,表示 与 之间有一条边。 接下来 行读入整数 ,表示 限制的数量。 接下来 行,每行两个整数 , ,表示一条限制。 接下来 行读入整数 ,表示 限制的数量。 接下来 行,每行两个整数 , ,表示一条 限制。
输出格式(color.out)
一行一个整数,表示答案。
输入样例
3
1 2
1 3
2
2 1
3 1
2
2 1
3 1
输出样例
2
数据范围
对于 的数据,满足 。 对于再 的数据,满足 。 对于 的数据,满足 。
0809
- Status
- Done
- Rule
- IOI
- Problem
- 4
- Start at
- 2024-8-9 9:00
- End at
- 2024-8-9 12:00
- Duration
- 3 hour(s)
- Host
- Partic.
- 28