提出 #67419508

---

ソースコード 拡げる

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

const int N = 3e3 + 10;

int n, fa[N], dep[N];
vector<int> e[N], a[N];
bool v[N][N];
string s;
int f[N], f2[N];
int ans;
int tp; pair<int, int> sta[N * N];

int times;

int findfa(int x) {
    return x == f[x] ? x : f[x] = findfa(f[x]);
}
int findfa2(int x) {
    return x == f2[x] ? x : f2[x] = findfa2(f2[x]);
}
void merge(int x, int y) {
    while (findfa2(x) != findfa2(y)) {
        times++;
        f[findfa(x)] = findfa(y);
        f2[findfa2(x)] = findfa2(y);
        if (dep[x] == 1) break;
        x = fa[x], y = fa[y];
    }
}

void dfs(int x) {
    for (int y : a[dep[x]]) if (v[x][y]) {
        merge(x, y);
    }
    for (int y : e[x]) {
        if (y == fa[x]) continue;
        fa[y] = x;
        dep[y] = dep[x] + 1;
        dfs(y);
    }
}
void dfs2(int x) {
    a[dep[x]].push_back(x);
    for (int y : e[x]) {
        if (y != fa[x]) {
            dfs2(y);
        }
    }
}
void dfs3(int x) {
    for (int y : a[dep[x]]) if (findfa(x) == findfa(y)) {
        if (dep[x] == 0 || v[fa[x]][fa[y]]) {
            v[x][y] = 1;
            ans += 2;
            sta[++tp] = {x, y};
        }
    }
    for (int y : e[x]) {
        if (y == fa[x]) continue;
        fa[y] = x;
        dep[y] = dep[x] + 1;
        dfs3(y);
    }
}

int main() {
    // freopen("big.in", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) {
        cin >> s; s = "#" + s;
        for (int j = 1; j <= n; j++) {
            v[i][j] = s[j] - '0';
        }
    }
    for (int i = 1; i <= n; i++) f[i] = i;
    for (int x = 1; x <= n; x++) {
        for (int i = 0; i <= n; i++) {
            a[i].clear();
            fa[i] = dep[i] = 0;
            f2[i] = i;
        }
        for (int y : e[x]) {
            fa[y] = x;
            dep[y] = 1;
            dfs(y);
            dfs2(y);
        }
    }
    for (int x = 1; x <= n; x++) for (int y : e[x]) if (x < y) {
        for (int i = 0; i <= n; i++) {
            a[i].clear();
            fa[i] = dep[i] = 0;
            f2[i] = i;
        }
        fa[x] = y, fa[y] = x;
        dep[x] = dep[y] = 1;
        dfs(x);
        dfs2(x);
        dfs(y);
    }
    ans = n;
    memset(v, 0, sizeof(v));
    for (int x = 1; x <= n; x++) {
        for (int i = 0; i <= n; i++) {
            fa[i] = dep[i] = 0;
            a[i].clear();
        }
        v[x][x] = 1;
        for (int y : e[x]) {
            fa[y] = x; dep[y] = 1;
            dfs3(y);
            dfs2(y);
        }
        v[x][x] = 0;
        while (tp) {
            v[sta[tp].first][sta[tp].second] = 0;
            tp--;
        }
    }
    for (int x = 1; x <= n; x++) for (int y : e[x]) if (x < y) {
        for (int i = 0; i <= n; i++) {
            a[i].clear();
            fa[i] = dep[i] = 0;
        }
        fa[x] = y, fa[y] = x;
        dfs3(x);
        dfs2(x);
        dfs3(y);
        while (tp) {
            v[sta[tp].first][sta[tp].second] = 0;
            tp--;
        }
    }
    cout << ans << "\n";
    return 0;
}

提出情報

ジャッジ結果