2020-2021 ACM-ICPC Brazil Subregional Programming Contest I Interactivity

题目描述

https://codeforces.com/gym/102861/problem/I

Solution

我们注意到最少询问次数就是叶子节点的个数

如果某个叶子没有选，则一定要选这个叶子到根的路径上的一个点

所以我们令 $f[u][0/1]$ 表示子树 $u$ 内是否还需要一次询问

转移大概是这样 $f[u][0] = \prod f[v][0] + \sum \frac{\prod f[v][0]}{f[v][0]} f[v][1]$

$f[v][1]=\sum \frac{\prod f[v][0]}{f[v][0]} f[v][1]$

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define maxn 100010
#define ll long long
using namespace std;

const int p = 1000000007;

int n, m;

struct Edge {
    int to, next;
} e[maxn]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

ll f[maxn][2], suf[maxn], pre[maxn];
void dfs(int u) {
    vector<int> a(1), b(1);
    ll s1 = 1, s2 = 0;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; dfs(v);
        a.push_back(f[v][0]); b.push_back(f[v][1]); 
        s1 = s1 * f[v][0] % p; 
    } int sz = a.size() - 1; pre[0] = suf[sz + 1] = 1; 
    for (int i = 1; i <= sz; ++i) pre[i] = pre[i - 1] * a[i] % p;
    for (int i = sz; i; --i) suf[i] = suf[i + 1] * a[i] % p; 
    for (int i = 1; i <= sz; ++i) s2 = (s2 + pre[i - 1] * suf[i + 1] % p * b[i]) % p;
    f[u][0] = (s1 + s2) % p; f[u][1] = s2;
    if (!sz) f[u][0] = f[u][1] = 1; 
}

int main() { fill(head, head + maxn, -1); 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 2; i <= n; ++i) {
        int x; cin >> x;
        add_edge(x, i);
    } dfs(1); cout << f[1][0] << "\n"; 
    return 0;
}