题目链接: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 ;
}