P11189 「KDOI-10」水杯降温

P11189 「KDOI-10」水杯降温 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

庆贺吧，第一个真正意义上的自己干出来的紫题。总用时 4h。

时间复杂度 \(O(n\log n)\)，对于每个点我们去找它可以吹气的最大次数和最小次数。如果一个点的最小次数大于它的最大次数，或者在计算父节点 u 最大次数时 j 减去的次数大于 j 最大次数，那么不可能成功吹冷。其余情况都可以吹冷。

对于最大次数采用二分验证答案方法，设当前减去的总数为 k，那么 \(m = a[u]\) 就会变成 m - k，一般 k 是大于 m 的，为了让 m 变为 0，需要总体加热 k - m。那么对于子节点来说，这些子节点最多减少 k 次，同时都必须加上 k - m，那么对每一个 j 判断，如果 \(b = a[j]\)，b + k - m 如果大于 0，那么 j 就必须减去 s = b + k - m 个，我们就让 k 减去 s，如果 k - s 小于 0，说明我们需要的减不够，那么这种状态就不行，注意，如果 s 超过了 j 的最大次数，也是不行的。不断进行。特别的如果 u 是叶节点，那么它的最大次数无穷大。求出了最大合适的 k 之后需要和子节点最大次数之和比对，取比较小的那个最为 u 的最大次数。因为最大不能超过子节点的最大限度。

对于最小次数，则是子节点最小次数之和与当前 \(a[u]\) 中，大的那个。因为需要满足双方最小。

对于最大次数，可以为负数，为了判断如，这种情况：

0
1
2
1
-2 -1
s

综上写出代码即可。较短。

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

typedef long long LL;

const int N = 500010;
const LL INF = 1e12 + 10;

int h[N], ne[N], e[N], idx;
int n, m, key = 601;
LL a[N], cnt[N], low[N];

bool check(LL u, LL k)
{
    LL res = k;
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        LL s = k - a[u] + a[j];
        if (s > cnt[j]) return false; // 需要减去的不能超过它能承受的最大的
        if (s > 0) res -= s;
        if (res < 0) return false;
    }
    return true;
}

LL find1(LL u)
{
    LL l = -INF, r = INF;
    
    while (l < r)
    {
        LL mid = l + r + 1 >> 1;
        if (check(u, mid)) l = mid;
        else r = mid - 1;
    }
    
    return l;
}

bool dfs(int u)
{
	LL sum = 0, sum2 = 0;
	bool flag = 0;
	for (int i = h[u]; i != -1; i = ne[i])
	{
		int j = e[i];
		if (dfs(j)) return true;
		sum += low[j];
		sum2 += cnt[j];
		flag = true;
 	}
	if (flag) 
	{
	    cnt[u] = min(find1(u), sum2);
	   // cout << 'a';
	   //cout << find1(u) << endl;
	}
	else cnt[u] = INF;
	
	if (flag) low[u] = max(sum, a[u]);
	else low[u] = -INF;
// 	printf("%d %lld %lld\n", u, low[u], cnt[u]);
	if (low[u] > cnt[u]) return true;
	return false;
}

void add(int a, int b)
{
	e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int main()
{
	int T;
	cin >> T >> T;
	for (int u = 1; u <= T; u ++ )
	{

		cin >> n;
		idx = 0;
		for (int i = 0; i <= n; i ++ ) 
		{
			h[i] = -1;
		}
		for (int i = 2; i <= n; i ++ ) 
		{
			int x;
			cin >> x;
			add(x, i);
		}
		for (int i = 1; i <= n; i ++ ) 
		{
			scanf("%lld", &a[i]);
		} 
		int flag = dfs(1);
		if (flag) puts("Shuiniao");
		else puts("Huoyu");
	}
	
	return 0;
}


/*
hack

0
1
2
1
-2 -1
s

0
1
7
1 2 2 3 3 5 
21 18 16 -80 14 2 12
s

0
1
7
1 2 2 3 2 3 
1206191 1201814 1172698 -778167 116182 -2139946 1052140 
s

0
1
7
1 2 2 3 3 5 
1347945 1347877 1347443 -536656 1344473 2906 1240697 
s

*/