KDOI-10 컵 냉각 문제 - 로그우 플랫폼 (luogu.com.cn)

O(n log n) 시간 복잡도를 가진 알고리즘으로, 각 노드에 대해 최대 및 최소 공기 배출 횟수를 계산합니다. 특정 노드의 최소 횟수가 최대 횟수를 초과하거나 부모 노드 u의 최대 횟수 계산 시 j에서 감소한 값이 허용 범위를 넘으면 냉각 불가능합니다. 그 외 경우는 가능합니다.

최대 횟수 계산은 이분 탐색을 활용합니다. 현재 감소량을 k로 가정하면 a[u]는 m - k로 변경됩니다. 일반적으로 k가 m보다 큽니다. m을 0으로 만드려면 전체적으로 (k - m)만큼 추가 가열해야 합니다. 자식 노드는 최대 k만큼 감소 가능하며, 이에 따라 (k - m)을 추가로 계산해야 합니다. 각 j에 대해 a[j] + (k - m)이 0보다 크면 s = a[j] + (k - m)만큼 감소시켜야 합니다. k - s가 음수이거나 j의 최대 감소량을 초과하면 실패합니다. 단, 리프 노드의 경우 최대 횟수는 무한대입니다. 최대 k 값을 구한 후 자식 노드의 최대 횟수와 비교하여 더 작은 값을 선택합니다.

최소 횟수는 자식 노드의 최소 횟수 합과 a[u] 중 큰 값을 선택합니다. 두 조건을 동시에 만족해야 합니다.

음수 값 처리를 위해 다음과 같은 예외 상황을 고려해야 합니다:

0
1
2
1
-2 -1
s

다음은 구현 코드입니다.

#include
#include
#include
#include
#include

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 validate(LL node, LL total)
{
LL remaining = total;
for (int i = h[node]; i != -1; i = ne[i])
{
int child = e[i];
LL required = total - a[node] + a[child];
if (required > cnt[child]) return false;
if (required > 0) remaining -= required;
if (remaining < 0) return false;
}
return true;
}

LL computeMax(LL node)
{
LL left = -INF, right = INF;

while (left < right)
{
LL mid = left + right + 1 >> 1;
if (validate(node, mid)) left = mid;
else right = mid - 1;
}

return left;
}

bool traverse(int node)
{
LL sum = 0, sum2 = 0;
bool hasChild = false;
for (int i = h[node]; i != -1; i = ne[i])
{
int child = e[i];
if (traverse(child)) return true;
sum += low[child];
sum2 += cnt[child];
hasChild = true;
}
if (hasChild)
{
cnt[node] = min(computeMax(node), sum2);
}
else cnt[node] = INF;

if (hasChild) low[node] = max(sum, a[node]);
else low[node] = -INF;

return low[node] > cnt[node];
}

void insertEdge(int parent, int child)
{
e[idx] = child, ne[idx] = h[parent], h[parent] = 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;
insertEdge(x, i);
}
for (int i = 1; i <= n; i ++ )
{
scanf("%lld", &a[i]);
}
int result = traverse(1);
if (result) puts("Shuiniao");
else puts("Huoyu");
}

return 0;
}