概要

比赛地址

2020牛客暑期多校训练营（第十场）

题目

A

B

C

D

E

F

G

H

I

J. Identical Trees

题目大意

给定两棵标号有根树，问最少修改某棵树中多少个节点可以使两棵树完全一致。
保证两棵树同构。

解题思路

考虑树形dp。最开始已知两棵树同构。考虑两个根结点的所有子树，设 dp[u][v] 表示将第一棵树以 u 为根结点的子树变成第二棵树以 v 为根结点的子树一样的代价。则答案为 dp[rt1][rt2]。
我们令两颗不同构的树标号变成一样的代价为 INF。这里可以通过提前判断两颗树的 size 是否相同，不同则直接设置匹配代价为 INF。同构的树之间匹配的代价通过树形dp可以计算获得。不同构的树，其子树不存在完美匹配，因此匹配的代价也为 INF，并不需要通过树哈希来判断。
考虑转移。通过KM跑二分图最小权完美匹配，可以进行dp转移。

AC代码

#include <bits/stdc++.h>
using namespace std;
const int N = 510;
const int INF = 1e7;

struct KM {
    int w[N][N], lx[N], ly[N];
    int slack[N];
    int linker[N], pre[N];
    int n;
    bool vis[N];
    void init(int n) {
        this->n = n;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                w[i][j] = -INF;
            }
        }
    }
    void bfs(int x) {
        int y = 0, nex = 0;
        int d;
        for (int i = 1; i <= n; i++) {
            pre[i] = 0;
            vis[i] = false;
            slack[i] = INF;
        }
        linker[y] = x;
        while (true) {
            x = linker[y]; d = INF; vis[y] = true;
            for (int i = 1; i <= n; i++) {
                if (!vis[i]) {
                    if (slack[i] > lx[x] + ly[i] - w[x][i]) {
                        slack[i] = lx[x] + ly[i] - w[x][i];
                        pre[i] = y;
                    }
                    if (slack[i] < d) {
                        d = slack[i];
                        nex = i;
                    }
                }
            }
            for (int i = 0; i <= n; i++) {
                if (vis[i]) {
                    lx[linker[i]] -= d;
                    ly[i] += d;
                }
                else slack[i] -= d;
            }
            y = nex;
            if (linker[y] == -1) break;
        }
        while(y) {
            linker[y] = linker[pre[y]];
            y = pre[y];
        }
    }
    long long solve() {
        long long rs = 0;
        for (int i = 1; i <= n; i++) {
            lx[i] = ly[i] = 0;
            linker[i] = -1;
        }
        for (int i = 1; i <= n; i++) {
            bfs(i);
        }
        for (int i = 1; i <= n; i++) {
            rs += lx[i] + ly[i];
        }
        return rs;
    }
}km;

vector<int> G[2][N];
int rt[2];

int f[N][N];
int dp(int x, int y) {
    if (f[x][y] >= 0) {
        return f[x][y];
    }
    if (G[0][x].size() != G[1][y].size()) {
        return f[x][y] = INF;
    }
    f[x][y] = (x != y);
    for (int a : G[0][x]) {
        for (int b : G[1][y]) {
            dp(a, b);
        }
    }
    int sz = (int)G[0][x].size();
    km.init(sz);
    for (int i = 0; i < sz; i++) {
        for (int j = 0; j < sz; j++) {
            int a = G[0][x][i], b = G[1][y][j];
            km.w[i + 1][j + 1] = -f[a][b];
        }
    }
    int ans = (int)km.solve();
    return f[x][y] = min(f[x][y] - ans, INF);
}

int main(int argc, const char * argv[]) {
    int n; scanf("%d", &n);
    memset(f, -1, sizeof(f));
    for (int j = 0; j < 2; j++) {
        for (int i = 1, x; i <= n; i++) {
            scanf("%d", &x);
            if (x) G[j][x].push_back(i);
            else rt[j] = i;
        }
    }
    printf("%d\n", dp(rt[0], rt[1]));
    return 0;
}