NC14312. Color a Tree
描述
输入描述
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 tree’s 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.
输出描述
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.
示例1
输入:
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
输出:
2 -1
C++ 解法, 执行用时: 57ms, 内存消耗: 6008K, 提交时间: 2021-10-05 14:10:53
#include<bits/stdc++.h>
using namespace std;
const int N=100001;
int n,h[N],to[N*2],nx[N*2],in[N],ou[N],mid,l[N],r[N],flag;
void dfs(int p,int pr){
l[p]=in[p],r[p]=mid-ou[p];
int sa=0,sb=1;
for(int i=h[p];i;i=nx[i])
if(to[i]!=pr){
dfs(to[i],p);
sa+=l[to[i]],sb+=r[to[i]];
}
l[p]=max(l[p],sa),r[p]=min(r[p],sb);
if(l[p]>r[p]) flag=0;
}
int main(){
int $;
for(scanf("%d",&$);$--;){
scanf("%d",&n);
for(int i=1;i<=n;++i) h[i]=in[i]=ou[i]=0;
for(int i=1,u,v,tt=0;i<n;++i){
scanf("%d%d",&u,&v);
to[++tt]=v,nx[tt]=h[u],h[u]=tt;
to[++tt]=u,nx[tt]=h[v],h[v]=tt;
}
int _;scanf("%d",&_);
for(int i=1,x,y;i<=_;++i)
scanf("%d%d",&x,&y),in[x]=max(in[x],y);
scanf("%d",&_);
for(int i=1,x,y;i<=_;++i)
scanf("%d%d",&x,&y),ou[x]=max(ou[x],y);
int s=0,t=n+1;
while(s<t){
mid=s+t>>1;
flag=1,dfs(1,0);
if(flag&&l[1]<=mid&&r[1]>=mid) t=mid;
else s=mid+1;
}
printf("%d\n",s<=n?s:-1);
}
return 0;
}