2017 CCPC 哈尔滨站 题解

题目链接  2017 CCPC Harbin

Problem A

Problem B

Problem D

Problem F

Problem L

考虑二分答案。

设当前待验证的答案为x

我们可以把第二个条件转化为在子树中最多有几个点是黑色的。

那么我们可以根据这些条件求出以每个点为根的子树的黑点数范围，做一次dfs。

最后看看根结点的范围是否包含x即可。

#include <bits/stdc++.h>

using namespace std;

#define rep(i, a, b)	for (int i(a); i <= (b); ++i)

#define dec(i, a, b)	for (int i(a); i >= (b); --i)

#define MP		make_pair

#define fi		first

#define se		second

typedef long long LL;

typedef pair <int, int> PII;

const int N = 1e5 + 10;

int sz[N];

int T, n;

int lima, limb;

int l, r;

int flag;

int c[N], d[N], cc[N], dd[N];

vector <int> v[N];

PII la[N], lb[N];

void dfs(int x, int fa){

	sz[x] = 1;

	for (auto u : v[x]){

		if (u == fa) continue;

		dfs(u, x);

		sz[x] += sz[u];

	}

}

void calc(int x, int fa){

	int xx = 0, yy = 1;

	for (auto u : v[x]){

		if (u == fa) continue;

		calc(u, x);

		xx += c[u], yy += d[u];

	}

	c[x] = max(c[x], xx);

	d[x] = min(d[x], yy);

}

bool check(int x){

	rep(i, 1, n) c[i] = cc[i], d[i] = dd[i];

	rep(i, 1, lima) c[la[i].fi] = max(c[la[i].fi], la[i].se);

      	rep(i, 1, limb) d[lb[i].fi] = min(d[lb[i].fi], x - lb[i].se);

	calc(1, 0);

	rep(i, 1, n) if (c[i] > d[i]) return false;

	if (x >= c[1] && x <= d[1]) return true; else return false;

}

int main(){

	scanf("%d", &T);

	while (T--){

		scanf("%d", &n);

		rep(i, 0, n + 1) v[i].clear();

		rep(i, 2, n){

			int x, y;

			scanf("%d%d", &x, &y);

			v[x].push_back(y);

			v[y].push_back(x);

		}

		rep(i, 0, n + 1) sz[i] = 0;

		dfs(1, 0);

		rep(i, 1, n) cc[i] = 0, dd[i] = sz[i];

		flag = 1;

		scanf("%d", &lima);

		rep(i, 1, lima){

			scanf("%d%d", &la[i].fi, &la[i].se);

			if (sz[la[i].fi] < la[i].se){

				flag = 0;

			}

		}

		scanf("%d", &limb);

		rep(i, 1, limb){

			scanf("%d%d", &lb[i].fi, &lb[i].se);

			if (n - sz[lb[i].fi] < lb[i].se){

				flag = 0;

			}

		}

		if ((!flag) || (!check(n))){

			puts("-1");

			continue;

		}

		l = 0, r = n;

		while (l + 1 < r){

			int mid = (l + r) >> 1;

			if (check(mid)) r = mid;

			else l = mid + 1;

		}

		if (check(l)) printf("%d\n", l);

		else printf("%d\n", r);

	}

	return 0;

}

　　

Problem M

2017 CCPC 哈尔滨站 题解的相关教程结束。