题解 | #小H学生物#

设 表示根到 的异或和， 可以表示为：

展开可以得到：

其中，每个 的系数为：和 只有当 之和 为奇数时， 才会被异或到最终的基因多样性中。

#include <bits/stdc++.h>

using namespace std;

const int N = 100;

using Gen = bitset<N>;
using piG = pair<int, Gen>;
using vpiG = vector<piG>;
void solve()
{
    int n, m, L;
    cin >> n >> m >> L;

    vector<vpiG> tree(n + 1, vpiG());

    for (int i = 1; i < n; i++)
    {
        int u, v;
        string s;
        cin >> u >> v >> s;
        Gen g;
        for (int j = 0; j < L; j++)
        {
            if (s[j] == '1')
                g.set(L - 1 - j);
        }
        tree[u].pb({v, g});
    }

    vector<Gen> A(n + 1, Gen());
    queue<int> q;
    q.push(1);

    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto &[v, g] : tree[u])
        {
            A[v] = A[u] ^ g;
            q.push(v);
        }
    }

    vector<int> a(m);
    for (int i = 0; i < m; i++)
    {
        cin >> a[i];
    }

    Gen genes;
    genes.reset();
    for (int k = 1; k <= m; k++)
    {
        int c = 0;
        if (k <= m - 2)
            c += (m - k - 1);
        if (k >= 3)
            c += (k - 2);
        if (c & 1)
            genes ^= A[a[k - 1]];
    }

    string ans = genes.to_string();
    ans = ans.substr(N - L, L);
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0);
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    int _ = 1;
    // std::cin >> _;
    while (_--)
    {
        solve();
    }
    return 0;
}