模拟赛总结

编号	总分	A题	B题	C题	D题
8	83	62	0	13	8
用时	03:00:00	06:33:43	11:22:23	99:99:99	99:99:99

A. BOSS树：拓扑排序与子树贪心

本题使用拓扑排序思想，结合子树大小进行贪心决策。核心在于利用优先队列每次选取子树最大的节点处理。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 1e5 + 5;
int n, m, inDegree[MAXN], subSize[MAXN];
vector<int> adj[MAXN];
struct Element {
    int idx;
};
vector<int> layers[MAXN];
int layerCount = 0;
vector<Element> temp;

bool operator < (const Element &a, const Element &b) {
    return subSize[a.idx] < subSize[b.idx];
}

priority_queue<Element> pq;

void calcSubsize(int u, int parent) {
    subSize[u] = 1;
    for (int v : adj[u]) {
        calcSubsize(v, u);
        subSize[u] += subSize[v];
    }
}

signed main() {
    freopen("boss.in", "r", stdin);
    freopen("boss.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n >> m;
    for (int i = 2; i <= n; i++) {
        int f;
        cin >> f;
        adj[f].push_back(i);
        inDegree[i]++;
    }
    calcSubsize(1, 0);
    pq.push({1});
    
    while (!pq.empty()) {
        ++layerCount;
        for (int cnt = 1; cnt <= m && !pq.empty(); cnt++) {
            Element cur = pq.top();
            pq.pop();
            int u = cur.idx;
            layers[layerCount].push_back(u);
            for (int v : adj[u]) {
                inDegree[v]--;
                if (inDegree[v] == 0) temp.push_back({v});
            }
        }
        while (!temp.empty()) {
            pq.push(temp.back());
            temp.pop_back();
        }
    }
    
    cout << layerCount << '\n';
    for (int i = 1; i <= layerCount; i++) {
        cout << layers[i].size() << ' ';
        for (int x : layers[i]) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

B. 黄金树召唤：树上概率DP

本题使用两轮DFS进行树形动态规划。第一轮计算每个节点的概率值，第二轮使用递推修正每个节点的最终答案。

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 5e5 + 5;
int n, value[MAXN];
double prob[MAXN];
vector<int> edges[MAXN];
double dp[MAXN], result[MAXN], selfVal[MAXN], childSum[MAXN];

void dfs1(int u) {
    dp[u] = prob[u];
    for (int v : edges[u]) {
        dfs1(v);
        dp[u] *= (1 - dp[v]);
    }
}

void dfs2(int u) {
    result[u] = selfVal[u];
    for (int v : edges[u]) {
        selfVal[v] = childSum[u];
        double parentProduct = dp[u] / (1 - dp[v]);
        childSum[v] = (selfVal[u] + value[u]) * parentProduct 
                     + childSum[u] * (1 - parentProduct);
        dfs2(v);
    }
}

signed main() {
    freopen("tree.in", "r", stdin);
    freopen("tree.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    cin >> n;
    for (int i = 2; i <= n; i++) {
        int p;
        cin >> p;
        edges[p].push_back(i);
    }
    for (int i = 1; i <= n; i++) cin >> prob[i];
    for (int i = 1; i <= n; i++) cin >> value[i];
    
    dfs1(1);
    dfs2(1);
    
    double total = 0;
    for (int i = 1; i <= n; i++) total += max(0.0, result[i] * dp[i]);
    printf("%.6lf\n", total);
    
    return 0;
}