HDU 4274 Spy's Work：樹形 DP 維護區間檢測薪資信息矛盾

問題描述

公司結構為樹（1 為根），第 i 部門包含節點 i 及其所有子孫。間諜給出 M 條信息：某部門薪資總和 < / > / = w。每人薪資 ≥ 1。判斷信息是否自相矛盾。

樹形 DP 狀態定義

• min[u]：子樹 u 的最小可能薪資和；
• max[u]：子樹 u 的最大可能薪資和。

初始：min[u] = 1（自身至少 1），max[u] = INF。
遞歸合併：min[u] = max(min[u], 1 + Σ min[v])，max[u] = min(max[u], Σ max[v])（若無額外約束則不改變）。
若任意節點出現 min[u] > max[u]，即矛盾。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 10007;
const long long INF = 4e18;

struct Edge { int to, next; } e[MAXN];
int head[MAXN], ecnt;
long long mn[MAXN], mx[MAXN];
bool bad;

void addEdge(int u, int v) { e[ecnt] = {v, head[u]}; head[u] = ecnt++; }

void dfs(int u) {
    long long sumMin = 1; // 自身至少 1
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to;
        dfs(v);
        sumMin += mn[v];
    }
    mn[u] = max(mn[u], sumMin);
    if (mn[u] > mx[u]) bad = true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        ecnt = 0; fill(head, head+n+1, -1);
        for (int i = 1; i <= n; ++i) { mn[i] = 1; mx[i] = INF; }
        for (int i = 2; i <= n; ++i) {
            int p; cin >> p; addEdge(p, i);
        }
        int m; cin >> m;
        while (m--) {
            int x, w; char op;
            cin >> x >> op >> w;
            if (op == '<') mx[x] = min(mx[x], (long long)w - 1);
            else if (op == '>') mn[x] = max(mn[x], (long long)w + 1);
            else { mx[x] = min(mx[x], (long long)w); mn[x] = max(mn[x], (long long)w); }
        }
        bad = false;
        dfs(1);
        cout << (bad ? "Lie" : "True") << '\n';
    }
    return 0;
}

關鍵點

• 後序遍歷自底向上合併區間；
• 長整型防溢出（w ≤ 1e8, n ≤ 1e4，和 ≤ 1e12）；
• 若 mn[1] > mx[1] 也視為矛盾（根部門約束）。