某岛

… : "…アッカリ~ン . .. . " .. .
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;
    }
}