某島

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

POJ 3342. Party at Hali-Bula

接上題。

再開一個 dp 狀態,記錄是否是唯一解即可。
對 f1 合併狀態之後,狀態轉移果然變得十分對稱優雅。。。

const int N = int(1e4) + 9;
VI adj[N]; string s;
int f0[N],f1[N]; // 不取, 取 or 不取
bool g0[N],g1[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] += f1[v]; g0[u] &= g1[v];
        f1[u] += f0[v]; g1[u] &= g0[v];
    }
    f1[u] += 1;
    if (f1[u] < f0[u]) {
        f1[u] = f0[u];
        g1[u] = g0[u];
    } else if (f1[u] == f0[u]) {
        g1[u] = 0;
    }
}

map<string, int> H;

int h(const string s) {
    if (!CTN(H, s)) {
        int t = SZ(H);
        H[s] = t;
    }
    return H[s];
}

int main() {

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

    while (RD(n)) {
        REP(i, n) f0[i] = f1[i] = 0, g0[i] = g1[i] = 1, adj[i].clear();
        H.clear(); cin >> s; DO (n-1) {
            cin >> s; int x = h(s);
            cin >> s; int y = h(s);
            adj[x].PB(y);
            adj[y].PB(x);
        }
        dfs();
        printf("%d ", f1[0]);
        puts(g1[0] ? "Yes" : "No");
    }
}