HDU6241 17CCPC哈尔滨L

分手后的思念是犯贱 2023-10-11 13:27 26阅读 0赞

> http://acm.hdu.edu.cn/showproblem.php?pid=6241

二分判断答案，可以将原题目的限制转化为子树至多的点up和至少的点down，如果up >= down则说明当前情况可行。

比赛的时候觉得这种做法太简单了给Pass掉了(雾),事实上这种正确性是可以证明的，只要保证对于所有的l <= r以及l1 <= x <= r，则说明x个黑点的情况可行。

#include <map>
    #include <set>
    #include <ctime>
    #include <cmath>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <string>
    #include <bitset>
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <sstream>
    #include <iostream>
    #include <algorithm>
    #include <functional>
    using namespace std;
    #define For(i, x, y) for(int i=x;i<=y;i++)
    #define _For(i, x, y) for(int i=x;i>=y;i--)
    #define Mem(f, x) memset(f,x,sizeof(f))
    #define Sca(x) scanf("%d", &x)
    #define Sca2(x,y) scanf("%d%d",&x,&y)
    #define Sca3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define Scl(x) scanf("%lld",&x)
    #define Pri(x) printf("%d\n", x)
    #define Prl(x) printf("%lld\n",x)
    #define CLR(u) for(int i=0;i<=N;i++)u[i].clear();
    #define LL long long
    #define ULL unsigned long long
    #define mp make_pair
    #define PII pair<int,int>
    #define PIL pair<int,long long>
    #define PLL pair<long long,long long>
    #define pb push_back
    #define fi first
    #define se second
    typedef vector<int> VI;
    int read(){
        int x = 0,f = 1;char c = getchar();while (c<'0' || c>'9'){
        if (c == '-') f = -1;c = getchar();}
    while (c >= '0'&&c <= '9'){x = x * 10 + c - '0';c = getchar();}return x*f;}
    const double PI = acos(-1.0);
    const double eps = 1e-9;
    const int maxn = 2e5 + 10;
    const int INF = 0x3f3f3f3f;
    const int mod = 1e9 + 7;
    int N,M,K;
    struct Edge{
        int to,next;
    }edge[maxn * 2];
    int head[maxn],tot;
    void init(){
        for(int i = 0 ; i <= N; i ++) head[i] = -1;
        tot = 0;
    }
    void add(int u,int v){
        edge[tot].to = v;
        edge[tot].next = head[u];
        head[u] = tot++;
    }
    LL l[maxn],r[maxn],up[maxn],down[maxn],sz[maxn];
    void dfs(int sum,int u,int la){
        LL L = 0 ,R = 0; sz[u] = 1;
        down[u] = l[u]; up[u] = sum - r[u];
        for(int i = head[u]; ~i ; i = edge[i].next){
            int v = edge[i].to;
            if(v == la) continue;
            dfs(sum,v,u);
            sz[u] += sz[v];
            L += down[v]; R += up[v];
        }
        down[u] = max(down[u],L);
        up[u] = min(up[u],sz[u]);
        up[u] = min(up[u],R + 1);
    }
    bool check(int x){
        dfs(x,1,-1); bool flag = true;
        if(up[1] < x || down[1] > x) return false;
        for(int i = 1; i <= N ; i ++){
            if(up[i] < down[i]) return false;
        }
        return true;
    }
    int solve(){
        int l = 0,r = N;
        int ans = -1;
        while(l <= r){
            int m = l + r >> 1;
            if(check(m)){
                r = m - 1;
                ans = m;
            }else{
                l = m + 1;
            }
        }
        return ans;
    }
    int main(){
        int T; Sca(T);
        while(T--){
            Sca(N); init();
            for(int i = 1; i <= N ; i ++) l[i] = r[i] = 0;
            for(int i = 1; i <= N - 1; i ++){
                int u,v; Sca2(u,v);
                add(u,v); add(v,u);
            }
            Sca(M);
            while(M--){
                int p = read();LL num = read();
                l[p] = max(l[p],num);
            }
            Sca(M);
            while(M--){
                int p = read();LL num = read();
                r[p] = max(r[p],num);
            }
            Pri(solve());
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Hugh-Locke/p/11324108.html