ACM模版

描述

题解

典型的树归问题，复杂度 O(n2) 。

暂且不说树归部分，我们先考虑任何一种状态下如何求 S(e1,e2)2 。其实这里我们并不需要直接算出 A1、A2、B1、B2，只需要根据部分数据就能推出其他数据。
假如 A1 集合中有 n 个结点，那么 A2 集合中有 N - n 个结点。假如 B1 集合中有 m 个结点，那么 B2 集合中有 N-m 个结点。
假如 A1 与 B1 交集有 cnt 个结点，那么 A1 与 B2 交集有 n-cnt 个结点，那么 A2 与 B1 交集有 m-cnt 个结点，那么 A2 与 B2 交集有 N-m-n+cnt 个结点。
假如……那么……没了，这个部分就这样！

接着就是树归部分，如何枚举出所有情况？首先我们可以对 Tree1 的一个子树进行 dfs()，标记为集合 A1，然后在这个状态下对 Tree2 进行 dfs_()，这个部分就切切实实是树归了，在回溯的过程中进行上述规则的计数累加即可。

具体的还是要分析代码，理解了树归也就不难看懂代码了。

这里利用了 tuple 容器，如果不用这个容器就需要用到结构体指针了，毕竟 dfs_() 过程中要返回两个值，分别是 cnt 和 m。

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
#include <tuple>

using namespace std;

typedef long long ll;
typedef tuple<int, int> tii;

const int MAXN = 4e3 + 10;

int N;
int n;    // A1集合结点数
ll res = 0;

vector<int> tree[MAXN];
vector<int> tree_[MAXN];
tii tmp;

struct edge
{
    int u;
    int v;
} tr[MAXN], tr_[MAXN];

int vis[MAXN];

tii dfs_(int last, int root)
{
    int cnt = 0, m = 0;
    if (vis[root])
    {
        cnt++;
    }
    m++;
    int a, b;
    for (int i = 0; i < tree_[root].size(); i++)
    {
        if (tree_[root][i] != last)
        {
            tmp = dfs_(root, tree_[root][i]);
            tie(a, b) = tmp;
            cnt += a;
            m += b;
        }
    }
    if (m == N)
    {
        return make_tuple(cnt, m);
    }
    long long maxRes = 0;
    maxRes = max(maxRes, (ll)cnt * cnt);
    maxRes = max(maxRes, (ll)(n - cnt) * (n - cnt));
    maxRes = max(maxRes, (ll)(m - cnt) * (m - cnt));
    maxRes = max(maxRes, (ll)(N - m - n + cnt) * (N - m - n + cnt));
    res += maxRes;

    return make_tuple(cnt, m);
}

void dfs(int last, int root)
{
    vis[root] = 1;
    n++;
    for (int i = 0; i < tree[root].size(); i++)
    {
        if (tree[root][i] != last)
        {
            dfs(root, tree[root][i]);
        }
    }
}

int main(int argc, const char * argv[])
{
// freopen("/Users/zyj/Desktop/input.txt", "r", stdin);
    cin >> N;

    int u, v;
    for (int i = 1; i < N; i++)
    {
        scanf("%d%d", &u, &v);
        u++, v++;
        tree[u].push_back(v);
        tree[v].push_back(u);
        tr[i].u = u;
        tr[i].v = v;
    }
    for (int i = 1; i < N; i++)
    {
        scanf("%d%d", &u, &v);
        u++, v++;
        tree_[u].push_back(v);
        tree_[v].push_back(u);
        tr_[i].u = u;
        tr_[i].v = v;
    }

    for (int i = 1; i < N; i++)
    {
        n = 0;
        memset(vis, 0, sizeof(vis));
        dfs(tr[i].v, tr[i].u);
        dfs_(-1, 1);
    }

    cout << res << '\n';

    return 0;
}