boj/10502.cpp at main · joonghak/boj · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

#define ll long long
using namespace std;

const ll INF = 1e9 + 7;
const ll DIV = 987654321;

int n, m;
int k = 10;
int dp[2020];

bool A[1010][1010], noop[1010];
vector<int> adj[1010];

int go(int cur, int prv)
{

    int ret = 0;
    for (int nxt : adj[cur])
    {
        if (nxt == prv)
            continue;
        ret += go(nxt, cur);
    }

    memset(dp, 0, sizeof dp);
    memset(noop, 0, sizeof noop);
    for (int i = 0; i < adj[cur].size(); i++)
    {
        int a = adj[cur][i];

        if (a == prv)
            continue;
        noop[a] = 1;
        if (A[cur][a])
        {
            ret++;
        }
    }

    for (int i = 0; i < (1 << k); i++)
    {
        for (int j = 0; j < adj[cur].size(); j++)
        {
            for (int t = 0; t < adj[cur].size(); t++)
            {
                if (j != t && (i & (1 << j) && (i & (1 << t))))
                {
                    int a = adj[cur][j], b = adj[cur][t];
                    if (a == prv || b == prv || A[a][cur] || A[b][cur])
                        continue;
                    dp[i] = max(dp[i], dp[i ^ (1 << j) ^ (1 << t)] + (A[a][b]));
                }
            }
        }

    }

    int b = (1 << k) - 1;
    for (int i = 0; i < adj[cur].size(); i++)
    {
        int a = adj[cur][i];
        if (a == prv)
            continue;
        if (dp[b] == dp[(b ^ (1 << i))])
        {
            for (int j = 1; j <= n; j++)
            {
                if (j != a && A[a][j] && !A[cur][a] && !noop[j])
                {
                    A[a][j] = A[j][a] = 0;
                    A[cur][j] = A[j][cur] = 1;
                }
            }
        }
    }

    ret += dp[b];

    return ret;
}

int main()
{
    fastio;
    int t;
    cin >> t;
    while (t--)
    {
        memset(A, 0, sizeof A);

        cin >> n;
        for (int i = 0; i < n + 2; i++)
        {
            adj[i].clear();
        }
        for (int i = 0; i < n - 1; i++)
        {
            int a, b;
            cin >> a >> b;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }
        cin >> m;
        for (int i = 0; i < m; i++)
        {
            int a, b;
            cin >> a >> b;
            A[a][b] = A[b][a] = 1;
        }

        cout << go(1, -1) << "\n";
    }

    return 0;
}