题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6241

题意:给你一棵有 n 个结点的树,每个结点初始颜色都为白色,有 A 个条件:结点 x_i 的黑色结点数目不少于 y_i 个,同时有 B 个条件,除了结点 x_j 及其子树外至少有 y_j 个结点,求把最少要染成黑色结点的数目使得满足 A + B 个条件。

题解:参考自:https://blog.csdn.net/u013534123/article/details/78523559

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <bitset>
using namespace std;
#define ll long long
#define ull unsigned long long
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define pII pair<ll,ll>
#define pi acos(-1)
#define pb push_back
const double eps = 1e-;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int MAXN = 1e5 + ;
const int MAXM = 1e6 + ; int n;
vector<int>vec[MAXN];
int siz[MAXN],b[MAXN],mn[MAXN],mx[MAXN];
int up[MAXN],down[MAXN]; void init() {
for(int i = ; i <= n; i++) {
vec[i].clear();
b[i] = mn[i] = ;
}
} void getsize(int u,int fa) {
siz[u] = ;
for(int i = ; i < vec[u].size(); i++) {
int v = vec[u][i];
if(v == fa) continue;
getsize(v,u);
siz[u] += siz[v];
}
} bool dfs(int u,int fa) {
int l = , r = ;
for(int i = ; i < vec[u].size(); i++) {
int v = vec[u][i];
if(v == fa) continue;
if(!dfs(v,u)) return false;
l += down[v], r += up[v];
}
down[u] = max(l, mn[u]), up[u] = min(r, mx[u]);
return down[u] <= up[u];
} bool check(int x) {
for(int i = ; i <= n; i++) {
mx[i] = min(x - b[i],siz[i]);
if(mx[i] < ) return false;
}
return dfs(,) && down[] <= x && x <= up[];
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
#endif
int t;
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
init();
for(int i = ; i < n; i++) {
int u,v;
scanf("%d%d",&u,&v);
vec[u].pb(v);
vec[v].pb(u);
}
getsize(,);
int m;
bool flag = true;
scanf("%d",&m);
while(m--) {
int x,y;
scanf("%d%d",&x,&y);
mn[x] = max(mn[x],y);
if(y > siz[x]) flag = false;
}
scanf("%d",&m);
while(m--) {
int x,y;
scanf("%d%d",&x,&y);
b[x] = max(b[x],y);
if(y > n - siz[x]) flag = false;
}
if(!flag) {
puts("-1");
continue;
}
int l = , r = n, ans = -;
while(l <= r) {
int mid = (l + r) >> ;
if(check(mid)) ans = mid, r = mid - ;
else l = mid + ;
}
printf("%d\n",ans);
}
return ;
}

最新文章

  1. iOS静态分析举例
  2. shared memory realm does not exist
  3. OO.A.D.P
  4. Handler机制来处理子线程去更新UI线程控件
  5. 向 Web 开发人员推荐35款 JavaScript 图形图表库
  6. IAP Store Kit Guide(中文)
  7. Commons IO - IOUtils
  8. [BEC][hujiang] Lesson03 Unit1:Working life ---Grammar &amp; Listening &amp; Vocabulary
  9. Case When PK PIVOT
  10. cf437B The Child and Set
  11. 【网络流量最大流量】poj3281Dining
  12. 静态链表C语言数据结构
  13. 生鲜配送管理系统_升鲜宝V2.0 小标签打印功能【代配送商品打印小标签功能】说明_15382353715
  14. 对css盒模型的理解
  15. cocos2d-js 小知识
  16. [转]简单的动态修改RDLC报表页边距和列宽的方法
  17. 实验5 IIC通讯与AD/接DA接口
  18. XCode10.0遇到的问题
  19. ubuntu14.04 LTS 搜狗输入法安装和不能输入中文的解决方法
  20. python基础之3

热门文章

  1. 记:linux服务器启动重启WEB项目启动成功,长时间卡住未响应
  2. hanlp自然语言处理包的人名识别代码解析
  3. 打印 request 请求中的参数
  4. 【AtCoder】ARC064
  5. Intellj IDEA快捷键入门 之 Ctrl+Space(空格)
  6. 创建安全的 Netty 程序
  7. Caesar&#39;s Legions(CodeForces-118D) 【DP】
  8. # 滚动Hash
  9. thinkphp5.1路由设置小计
  10. 【转】STM32的FSMC详解