题目链接：传送门

Description

给一棵节点数为n，节点种类为k的无根树，问其中有多少种不同的简单路径，可以满足路径上经过所有k种类型的点？（a->b与b->a算作两条路径，起点与终点也可以相同）

Solution

点分治裸题 又是一个以前一直听起来很高大上实际上比较简单的方法 这道题可以状压，然后就把问题转化成了路径状态的或运算 剩下的就是点分治模板的事情了 大概就是找重心，计算过此根的答案，然后分治求解

Code

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int Maxn = 2e5 + 100, Maxm = 2048 + 10;

int N, M, K;
int e, Begin[Maxn], To[Maxn * 2], Next[Maxn * 2];
int size[Maxn];
int A[Maxn], Ans, Cnt[Maxm], Vis[Maxn];
int root, Max;

inline void Init()
{
    e = 0;
    Ans = 0;
    memset(size, 0, sizeof size);
    memset(Vis, 0, sizeof Vis);
    memset(Begin, 0, sizeof Begin);
}

inline void add_edge (int x, int y)
{
    To[++e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
}

inline void dfs (int x, int fa)
{
    size[x] = 1;
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (y == fa || Vis[y]) continue;
        dfs(y, x);
        size[x] += size[y];
    }
}

inline void dfs1 (int x, int fa, int Size)
{
    int tmp = 0;
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (y == fa || Vis[y]) continue;
        dfs1(y, x, Size);
        tmp = max(tmp, size[y]);
    }
    tmp = max(tmp, Size - size[x]);
    if (tmp < Max)
    {
        Max = tmp;
        root = x;
    }
}

int sum, rec[Maxn];

inline void dfs (int x, int fa, int state)
{
    Ans += Cnt[(~state) & ((1 << K) - 1)];
    rec[++sum] = state;
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (Vis[y] || y == fa) continue;
        dfs(y, x, state | (1 << A[y]));
    }
}

inline void Calc (int x)
{
    memset(Cnt, 0, sizeof Cnt);
    Cnt[0] = 1;
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (Vis[y]) continue;
        sum = 0;
        dfs(y, 0, (1 << A[x]) | (1 << A[y]));
        for (int j = 1; j <= sum; ++j)
            for (int k = 0; k < (1 << K); ++k)
            {
                if ((rec[j] | k) == rec[j])
                    Cnt[k] ++;
            }
    }
}

inline void Divide (int x)
{
    Max = INT_MAX;
    dfs(x, 0);
    dfs1(x, 0, size[x]);
    Vis[root] = 1;
    x = root;
    Calc(x);
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (Vis[y]) continue;
        Divide(y);
    }
}

main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    while (scanf("%lld%lld", &N, &K) != EOF)
    {
        Init();

        for (int i = 1; i <= N; ++i)
            scanf("%lld", &A[i]), A[i]--;

        for (int i =  1; i < N; ++i)
        {
            int x, y;
            scanf("%lld%lld", &x, &y);
            add_edge (x, y);
            add_edge (y, x);
        }

        Divide(1);
        Ans *= 2;
        if (K == 1) Ans += N;
        printf("%lld\n", Ans);
    }
    return 0;
}