某島

… : "…アッカリ~ン . .. . " .. .
March 10, 2020

POJ 2342. Anniversary party

樹的最大獨立集。

f0 表示當前節點不取
f1 表示當前節點取

樹 DP 即可。

const int N = int(1e4) + 9;
VI adj[N];
int f0[N], f1[N]; // 不取, 取
int n, p;

void dfs(int u = 0, int p = -1) {
#define v (*it)
    ECH(it, adj[u]) if (v != p) {
        dfs(v, u);
        f0[u] += max(f0[v], f1[v]);
        f1[u] += f0[v];
    }
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    while (RD(n)) {
        REP(i, n) RDD(f1[i]), f0[i] = 0, adj[i].clear();

        DO (n-1) {
            int x, y; RD(x, y); --x; --y;
            adj[x].PB(y);
            adj[y].PB(x);
        }
        dfs();
        cout << max(f0[0],f1[0]) << endl;
    }
}

我們發現這個 max(f0,f1) 好像有點煩。
不如把 f1 合併一下狀態,定義成可取可不取?
雖然對這個題的幫助並不明顯,不過在狀態更複雜的時候可就不一定了?Try POJ 3342. Party at Hali-Bula

const int N = int(1e4) + 9;
VI adj[N];
int f0[N], f1[N]; // 不取, 取 or 不取
int n, p;

void dfs(int u = 0, int p = -1) {
#define v (*it)
    ECH(it, adj[u]) if (v != p) {
        dfs(v, u);
        f0[u] += f1[v];
        f1[u] += f0[v];
    }
    checkMax(f1[u], f0[u]);
}

int main() {

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    while (RD(n)) {
        REP(i, n) RDD(f1[i]), f0[i] = 0, adj[i].clear();

        DO (n-1) {
            int x, y; RD(x, y); --x; --y;
            adj[x].PB(y);
            adj[y].PB(x);
        }
        dfs();
        cout << f1[0] << endl;
    }
}