记录编号	601044	评测结果	AAAAATTTTT
题目名称	4004.喵星人集会	最终得分	50
用户昵称	健康铀	是否通过	未通过
代码语言	C++	运行时间	23.183 s
提交时间	2025-05-27 14:52:15	内存使用	3.56 MiB

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> G;
vector<vector<int>> d;
int k, n;

struct KM {
    int n;
    vector<int> lx, ly, mt, sl;
    vector<bool> vx, vy;
    vector<vector<int>> g;
    KM(int sz, vector<vector<int>>& w) : n(sz), g(w) {
        lx.resize(n); ly.resize(n); mt.resize(n, -1);
        sl.resize(n); vx.resize(n); vy.resize(n);
        for (int i=0; i<n; ++i)
            lx[i] = *max_element(g[i].begin(), g[i].end());
    }
    bool dfs(int u) {
        vx[u]=1;
        for (int v=0; v<n; ++v) if (!vy[v]) {
            int gap=lx[u]+ly[v]-g[u][v];
            if (!gap) {
                vy[v]=1;
                if (mt[v]==-1 || dfs(mt[v])) 
                    return mt[v]=u, 1;
            } else sl[v] = min(sl[v], gap);
        }
        return 0;
    }
    int solve() {
        for (int u=0; u<n; ++u) {
            fill(sl.begin(), sl.end(), INT_MAX);
            while (1) {
                fill(vx.begin(), vx.end(), 0);
                fill(vy.begin(), vy.end(), 0);
                if (dfs(u)) break;
                int dt=INT_MAX;
                for (int v=0; v<n; ++v)
                    if (!vy[v]) dt=min(dt, sl[v]);
                for (int i=0; i<n; ++i) {
                    if (vx[i]) lx[i]-=dt;
                    if (vy[i]) ly[i]+=dt;
                    else sl[i]-=dt;
                }
            }
        }
        int res=0;
        for (int v=0; v<n; ++v)
            if (mt[v]!=-1) res += g[mt[v]][v];
        return res;
    }
};

void bfs(int s, vector<int>& dis) {
    queue<int> q{{s}};
    fill(dis.begin(), dis.end(), -1);
    dis[s]=0;
    while (!q.empty()) {
        int u=q.front(); q.pop();
        for (int v:G[u]) if (dis[v]==-1)
            dis[v]=dis[u]+1, q.push(v);
    }
}

void dfs(vector<int>& cur, unordered_set<int>& vs, unordered_set<int>& bd, vector<int>& s, int& res) {
    if (cur.size()==k) {
        int sz=k;
        vector<vector<int>> w(sz, vector<int>(sz));
        for (int i=0; i<sz; ++i)
            for (int j=0; j<sz; ++j)
                w[i][j] = -d[s[i]][cur[j]];
        KM km(sz, w);
        res = min(res, -km.solve());
        return;
    }
    auto can=bd;
    for (int u:can) if (!vs.count(u)) {
        auto nvs=vs, nbd=bd;
        nvs.insert(u); nbd.erase(u);
        for (int v:G[u]) if (!nvs.count(v))
            nbd.insert(v);
        cur.push_back(u);
        dfs(cur, nvs, nbd, s, res);
        cur.pop_back();
    }
}

int main() {
    freopen("party.in", "r", stdin);
    freopen("party.out", "w", stdout);

    string s;
    cin >> n >> s;
    G.resize(n+1);
    for (int i=1,u,v; i<n; ++i) {
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    vector<int> a;
    for (int i=1; i<=n; ++i)
        if (s[i-1]=='1') a.push_back(i);
    k=a.size();
    if (!k) return cout<<"QwQ",0;

    d.resize(n+1, vector<int>(n+1));
    for (int u=1; u<=n; ++u) {
        vector<int> dis(n+1);
        bfs(u, dis);
        d[u] = dis;
    }

    int res=INT_MAX;
    for (int st=1; st<=n; ++st) {
        vector<int> cur{st};
        unordered_set<int> vs{st}, bd;
        for (int v:G[st]) if (!vs.count(v))
            bd.insert(v);
        dfs(cur, vs, bd, a, res);
    }
    res==INT_MAX ? cout<<"QwQ" : cout<<res;
}