# hdu 6241 - zstu_zy的博客 - CSDN博客

Color a Tree

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 385 Accepted Submission(s): 86

Problem Description
Bob intends to color the nodes of a tree with a pen. The tree consists of N nodes. These nodes are numbered 1,2,…,N. The root of the tree is node 1. The initial color of each node is white. Bob can use one unit energy to color one node into black. To prevent Bob being lazy with painting, Alice proposed A+B rules. Each rule is represent by two numbers xi and yi.
For the first A rules, it means that there should be no less than yi nodes painted black for the subtree of node xi.
For the other B rules, it means that there should be no less than yi nodes painted black for all nodes except the subtree of node xi.
You need to help Bob to calculate the minimum energy he needs for the painting with all rules proposed by Alice satisfied.

Input
The first line is the number of test cases. For each test case, the first line contains one positive number N(1≤N≤100000), indicating the number of trees nodes.

The following N?1 lines describe the edges. Each line contains two integers u,v(1≤u,v≤N), denoting there is a edge between node u and node v.

The following one line contains one number A(A≤100000), indicating the first A rules.

The following A lines describe the first A rules. Each line contains two numbers xi and yi as described above.

The following one line contains one number B(B≤100000), indicating the other B rules.

The following B lines describe the other B rules. Each line contains two numbers xi and yi as described above.

Output
For each test case, output a integer donating the minimum energy Bob needs to use with all rules propose by Alice satisfied. If there is no solution, output ?1 instead.

Sample Input
2
5
1 2
2 3
3 4
1 5
2
2 1
5 1
1
2 1
5
1 2
2 3
3 4
1 5
3
1 2
2 2
5 1
1
3 5

Sample Output
2
-1

``````#include
#define LL long long
using namespace std;
const int N = 1e5+100;
int son[N];

LL l[N],r[N];
int tot;
int n,m,m2;

void dfs(int u,int f){
son[u] = 1;
int cns = 0;
for(int i = head[u];i != -1;i = nex[i]){
int v = num[i];
if(v == f) continue;
dfs(v,u);
son[u] += son[v];
cns += A[v];
}
A[u] = max(A[u],cns);
}
void check(int x,int u,int f){
l[u] = A[u],r[u] = min(son[u],x-B[u]);
LL cl = 0,cr = 0;
bool tmp= false;
for(int i = head[u];i != -1;i = nex[i]){
int v = num[i];
if(v == f) continue;
tmp = true;
check(x,v,u);
//l[u]+=l[v];r[u]+=r[v];
cl += l[v],cr += r[v];
}
l[u] = max(l[u],cl);
if(tmp) r[u] = min(cr+1,r[u]);
}

bool judge(int x){
check(x,1,-1);
bool tmp = true;
if(x < l || x > r) tmp = false;
for(int i = 1;i < n;i ++){
if(l[i] > r[i]) tmp = false;
}
return tmp;
}

int main(){
int T;
cin >> T;
while(T--){
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
tot = 0;
scanf("%d",&n);
for(int i = 1;i < n;i ++){
int u,v;
scanf("%d %d",&u,&v);
num[tot] = v;
num[tot] = u;
}

scanf("%d",&m);
for(int i= 1;i <= m;i ++){
int x,y;
scanf("%d %d",&x,&y);
A[x] = max(A[x],y);
}
scanf("%d",&m2);
for(int i = 1;i <= m2;i ++){
int x,y;
scanf("%d %d",&x,&y);
B[x] = max(B[x],y);
}
dfs(1,-1);
bool tmp= false;
for(int i = 1;i <= n;i ++){
if(A[i] > son[i]||B[i]+son[i] > n) {
tmp = true;
}
}
if(tmp){
puts("-1");
continue;
}
int l = -1,r = n;
for(int i = 1;i <= n;i ++) l = max(l,A[i]+B[i]);
l--;
while(r-l>1){
int mid = l+r>>1;
//cout << mid << ' '<< judge(mid) << endl;
if(judge(mid)) r = mid;
else l = mid;
}
//cout<<"!!" << endl;
cout << r << endl;
}
return 0;
}``````

(注：此网站文章大都来自公开的博客，如有原作者发现有侵权问题，请在此留言，我们会立刻删除相关文章。)