【题解】Color a Tree 二分答案+贪心 hdu6241 ——quhengyi11

传送门

没错题目名字一模一样（：

然而这是我在搜上一题的时候偶然遇到的一道题，觉得蛮好玩的就做了做

题目大意

给一棵节点全白的树，你要把它一些点涂黑，需要满足若干个形如在子树 $u_i$内有不少于$y_i$个黑点，在子树 $u_i$外有不少于$y_i$个黑点的限制，求最少黑点数

题解

注意到子树外的限制很麻烦，但是我们可以二分答案 $now$，把第二个限制转化为在子树 $u$内不多于 $y$个点，这样只需要判断每个点能放黑点数的上下界，然后 $dfs$合并就行。

记 $mx_u$为上界，$mn_u$为下界

$$mx_u=min(now-b[u],\sum_{v\in son_u}mx_v+1)$$

$$mn_u=max(a[u],\sum_{v\in son_u}min_v)$$

然后 $WA$了好几次，原因是它不保证 $x_i$互不相等，也就是说如果多个同样的限制条件限制同一个点，你需要取限制最大的那个。被坑了好久 $QwQ$

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<ctype.h>
#include<queue>
#include<map>
#define Re register
#define fo(i, a, b) for (Re int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (Re int i = (a); i >= (b); --i)
#define edge(i, u) for (Re int i = head[u], v = e[i].v; i; i = e[i].nxt, v = e[i].v)
#define pb push_back
#define F first
#define S second
#define ll long long
#define inf 1000000007
#define mp std::make_pair
#define eps 1e-4
#define mod 10000000 
#define lowbit(x) (x & -x)
#define N 101005
#define clr(arr) memset(arr, 0, sizeof arr)
#define bset std::bitset<N>
inline int read ()
{
    Re int x = 0; Re bool flag = 0; Re char ch = getchar();
    while (!isdigit(ch) && ch != '-') ch = getchar();
    if (ch == '-') flag = 1, ch = getchar();
    while (isdigit(ch)) x = (x << 3) + (x << 1) + (ch ^ 48), ch = getchar();
    if (flag) x = -x; return x;
}
int n, head[N], tot;
struct edge {
    int nxt, v;
} e[N << 1];
inline void addedge (int u, int v)
{
    e[++tot] = (edge) {head[u], v};
    head[u] = tot;
}
int now, mn[N], mx[N], a[N], b[N], A, B, sz[N];
bool flag;
inline void dfs (int u, int fa)
{
    sz[u] = 1;
    edge (i, u)
    {
        if (v == fa) continue;
        dfs(v, u);
        sz[u] += sz[v];
    }

    mx[u] = 1; mn[u] = 0;
    edge (i, u)
    {
        if (v == fa) continue;
        mx[u] += mx[v];
        mn[u] += mn[v];
    }

    mx[u] = std::min(mx[u], now - b[u]);
    mn[u] = std::max(a[u], mn[u]);
    if (mn[u] > mx[u] || mn[u] > now) flag = 0;
}
inline bool check ()
{
    flag = 1;
    dfs(1, 0);
    return flag && mn[1] <= now && now <= mx[1];
}
int main ()
{
    int T = read();
    while (T--)
    {
        n = read();
        clr(head); clr(a); clr(b); tot = 0;
        fo (i, 2, n)
        {
            int u = read(), v = read();
            addedge(u, v); addedge(v, u);
        }
        A = read();
        while (A--) 
        {
            int u = read();
            a[u] = std::max(read(), a[u]);
        }
        B = read();
        while (B--)
        {
            int u = read();
            b[u] = std::max(read(), b[u]);
        }
        int l = 0, r = n;
        while (l < r)
        {
            now = l + r >> 1;
            if (check()) r = now;
            else l = now + 1;
        }
        now = l;
        if (!check()) printf("-1\n"); 
        else printf("%d\n", l);
    }
    return 0;
}