HDU 6241 Color a Tree CCPC2017 Harbin（二分答案+上下界判定）

Color a Tree

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)

Total Submission(s): 92    Accepted Submission(s): 17

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

       

Source

2017中國大學生程式設計競賽-哈爾濱站-重制賽（感謝哈理工）

        CCPC哈爾濱，是一個二分答案專場……

        此題二分，B題二分，還有一個分數規劃的二分……

        這是一個非常值得借鑒的二分答案的題目。大緻題意：給你一棵樹，然後讓你對樹上的節點進行黑白染色。然後染色有一些要求，對于A類要求，要求在x的子樹中，至少有y個節點被染成了黑色；對于B類要求，要求在樹的所有節點除了x以及其子樹節點外，至少有y個節點被染成了黑色。初始狀态樹是白色的，現在問你，最少給多少個節點染成黑色之後，能夠滿足所有的A、B類要求。

        其實遇到這種至多至少，然後詢問最少的題目，應該就要想到上下界的判斷了。這種題目感覺之前見過，但是想不起來了。我們二分最後的染成黑色的節點數目，然後判定這個答案是否可行。我們發現，對于A類要求，相當于直接對節點x設定了一個下界，表示以他為根的子樹含有的黑色節點數目的下界。但是對于B類要求似乎不太好處理。這個時候可以利用轉化的思想。在非x以及其子樹的節點中至少包含y個黑色節點，那麼等價于在x以及其子樹的節點中至多包含n-y個黑色節點，由此，我們就可以以此為依據确定一個上界。這樣子的話，我們通過dfs，累加每一個兒子節點的上下界，再依此不斷縮小上下界。判定在過程中是否有出現上下界不合法的情況，以及我們枚舉的答案是否包含在根的上下界之中，來确定目前枚舉的答案的正确與否。

        具體實作過程中，我們要注意對于同一個點的要求可能會有多個，不能夠使其互相覆寫，而是應該保留特定的要求。因為這一點我倒是wa的好多次。具體見代碼：

#include<bits/stdc++.h>
#define N 101000

using namespace std;

int n,up[N],dw[N],d[N],u[N],b[N],sz[N];
vector<int> g[N];

void init()
{
    memset(g,0,sizeof(g));
    memset(b,0,sizeof(b));
    memset(dw,0,sizeof(dw));
}

bool dfs(int x,int fa)
{
    int down=0,UP=1;
    for(int i=0;i<g[x].size();i++)
    {
        int y=g[x][i];
        if (y==fa) continue;
        if (!dfs(y,x)) return 0;
        down+=d[y]; UP+=u[y];					//累加所有兒子的上下界
    }
    d[x]=max(dw[x],down);						//縮小上下界範圍
    u[x]=min(up[x],UP);
    return d[x]<=u[x];							//如果沖突，則目前枚舉答案不可行
}

void getsize(int x,int fa)
{
    sz[x]=1;
    for(int i=0;i<g[x].size();i++)
    {
        int y=g[x][i];
        if (y==fa) continue;
        getsize(y,x); sz[x]+=sz[y];
    }
}

bool check(int x)
{
    for(int i=1;i<=n;i++)
    {
        up[i]=min(x-b[i],sz[i]);
        if (up[i]<0) return 0;
    }
    return dfs(1,0)&&u[1]>=x&&d[1]<=x;					//最後要求枚舉的答案，在根的上下界範圍之内
}

int main()
{
    int T_T;
    cin>>T_T;
    while(T_T--)
    {
        init();
        scanf("%d\n",&n);
        for(int i=1;i<n;i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            g[u].push_back(v);
            g[v].push_back(u);
        }
        int m,flag=0;
        getsize(1,0);
        scanf("%d",&m);
        while(m--)
        {
            int x,y; scanf("%d%d",&x,&y);
            dw[x]=max(dw[x],y); if (y>sz[x]) flag=1;			//這裡注意這個至少的限制不能直接覆寫，而是取最大的
        }
        scanf("%d",&m);
        while(m--)
        {
            int x,y; scanf("%d%d",&x,&y);
            b[x]=max(y,b[x]);							//這裡也是同理
            if (y>n-sz[x]) flag=1;
        }
        if (flag){puts("-1");continue;}
        int l=0,r=n,ans=-1,mid;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if (check(mid)) ans=mid,r=mid-1;
                       else l=mid+1;
        }
        printf("%d\n",ans);
    }
}