线图
题目描述
九条可怜是一个热爱出题的女孩子。
今天可怜想要出一道和图论相关的题。在一张无向图 $G$ 上，我们可以对它进行一些非常有趣的变换，比如说对偶，又或者说取补。这样的操作往往可以赋予一些传统的问题新的活力。例如求补图的连通性、补图的最短路等等，都是非常有趣的问题。
最近可怜知道了一种新的变换：求原图的线图 (line graph)。对于无向图 $G = ⟨V, E⟩$，它的 线图 $L(G)$ 也是一个无向图：
- 它的点集大小为 $|E|$，每个点唯一对应着原图的一条边。
- 两个点之间有边当且仅当这两个点对应的边在原图上有公共点（注意不会有自环）。 下图是一个简单的例子，左图是原图，右图是它对应的线图。其中点 $1$ 对应原图的边 $(1, 2)$，点 $2$ 对应 $(1, 4)$，点 $3$ 对应 $(1, 3)$，点 $4$ 对应 $(3, 4)$。
经过一些初步的摸索，可怜发现线图的性质要比补图复杂很多，其中突出的一点就是补图 的补图会变回原图，而 $L(L(G))$ 在绝大部分情况下不等于 $G$ ，甚至在大多数情况下它的点数和 边数会以很快的速度增长。
因此，可怜想要从最简单的入手，即计算 $L^{k}(G)$ 的点数（其中 $L^{k}(G)$ 表示对 $G$ 求 $k$ 次线图）。 然而遗憾的是，即使是这个问题，对可怜来说还是太困难了，因此她进行了一定的弱化。她给出了一棵 $n$ 个节点的树 $T$，现在她想让你计算一下 $L^{k}(T)$ 的点数。
输入输出格式
输入格式：
第一行输入两个整数 $n$,$k$，表示树的点数以及连续求线图的次数。
接下来 $n − 1$ 行每行两个整数 $u$, $v$ 表示树上的一条边。
输出格式：
输出一行一个整数，表示答案对 $998244353$ 取模后的值。
样例一
input
5 3
1 2
2 3
2 5
3 4
output
5
explanation
如下图所示，左图为原树，中图为 $L(G)$，右图为 $L^{2}(G)$。这儿并未画出 $L^{3}(G)$，但是由于 $L^{2}(G)$ 有 $5$ 条边，因此 $L^{3}(G)$ 中有 $5$ 个点。
限制与约定
时间限制：3s
空间限制：512MB
这题的数据范围很有趣啊，谁叫标算的复杂度也是指数级的呢？
假如用人类智慧是容易做出前 30 分的，高水平的选手再发现一些性质能拿到 50 分，而显然我并不是，因为我在考场上只有 20 分。
那我们来看一看线图的高妙之处：
考虑 $L^{k}(G)$ 中的每一个点在 $G$ 中代表的形状。
- 显然，$L(G)$ 的点数对应了原图中的一条边。
- 容易发现，$L^{2}(G)$ 的点数对应了原图中的一条折线（即一对相邻的两条边）。
- 稍加推敲得到，$L^{3}(G)$ 的点数对应了原图中的一条长度为三的链或一组相互相邻的三条边。
以此类推不难发现，在 $L^{k}(G)$ 中的每一个点对应的是 $G$ 中的一个不超过 $k$ 条边的联通导出子图。由于原图 $G$ 是棵树，所以 $L^{k}(G)$ 中每一个点对应的是 $G$ 中的一颗边数不超过 $k+1$ 的子树。一个简单的结论是：两个结构相同（即同构）的导出子图，它们在 $L^{k}(G)$ 中对应的节点个数一定也是相同的。
于是我们考虑了一个初步的做法：
- 枚举所有的边数不超过 $k+1$ 的无根树，假设为 $T_{i}$，算出 $T_{i}$ 在 $L^{k}(G)$ 中对应的点数 $w_{i}$。
- 算出 $T_{i}$ 在 $G$ 中出现了的次数 $t_{i}$。
- $Ans = \sum\limits_{T_{i}}^{} w_{i} * t_{i}$。
枚举不同构的有根树可以枚举括号序列然后用树哈希来去重，因此主要考虑给定 $T_{i}$，如何 求解 $w_{i}$ 和 $t_{i}$。
求解 $w_{i}$ ：
因为 $T_{i}$ 的大小很小，我们能够求解 $L^{k}(T_{i})$ 的点数。但是这并不是我们要求的 $w_{i}$，因为这中的每一个点对应了 $T_{i}$ 中的每一个联通子图，也就是说这中间有 $T_{i}$ 的子图的贡献，我们需要减掉它们，我们可以 $O(2^{|T_{i}|})$ 枚举 $T_{i}$ 的子图，减掉它们的贡献，计算出 $w_{i}$ 的值。
容斥的复杂度并不是瓶颈，关键在于现在考虑如何求出 $L^{k}(T_{i})$ 的点数，如果暴力做的话，复杂度大概是 $O(k^{k})$，不太行。
我们可以沿用之前做部分分时的做法：
- $L(T_{i})$ 的点数是 $m$。
- $L^{2}(T_{i})$ 的点数是 $\sum\limits_{i \in V}^{} C_{d_{i}}^{2}$，其中 $d_{i}$ 为 $i$ 的度数。
- $L^{3}(T_{i})$ 的点数是 $\sum\limits_{(u,v) \in E}^{} (d_{u}-1)(d_{v}-1) + \sum\limits_{i \in V}^{} C_{d_{i}}^{3}$
- $L^{4}(T_{i})$ 的点数同样也可以用人类智慧直接算出来。
这样我们就只需要算 $L^{k-4}(T_{i})$ 就可以了。
这里有一个可以剪枝的地方，就是曾经算过的无根树与当前有同构时，就不必再算了。
求解 $t_{i}$：
想要直接把 $T_{i}$ 当无根树计算出它在另一个无根树 $G$ 中出现的次数是很难的，毕竟无根树的计数比有根树更复杂。
我们可以发现，如果我们把两颗无根树都当成有根树来做，即枚举有根树，却也是对的。因为无根树在另一颗无根树上一个成功的匹配，我们把某一棵无根树拉成有根树，另一棵无根树此时呈现出的有根形态一定会被枚举到恰好一次。于是问题得到了简化。
我们可以用树形dp直接解决它，由于 $T_{i}$ 的大小很小，用状压dp就可以了。
令 $f_{i,j}$ 为 $G$ 上第 $i$ 个点为第 $j$ 种有根树的根的嵌入方案数。
由于 $j$ 的孩子中可能存在两棵同构的子树，由于是没有标号的，故答案只能算一次，这是在dp时要注意的。然而我的实现方法并不优越，我的做法是，暴力合并所有同构的子树，每次dp时枚举之前所有状态中不包含这些同构子树中任意一个的状态。于是我就枚举子集了，复杂度变劣了一点。
然而在dp中有很多可以剪枝的地方，比如很显然，$i$ 的孩子数肯定不会少于 $j$ 的儿子数，或者在 $T_{i}$ 中存在一个子树和 $j$ 的子树同构，那可以不用重复计算了。
最后还有一个优化，就是当 $j$ 的亲生儿子中有叶子节点时，可以不用状压进去，直接用组合数算就可以啦。
于是我们就解决的这道题了，我在UOJ上勉强卡过去了，UOJ跑得还挺快的呢！反正我本地T飞了
#include <cstdio>
#include <map>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std; typedef long long LL;
typedef pair<int, int> Pair;
#define fir first
#define sec second
#define Mp make_pair
typedef vector<int>::iterator Vecit;
typedef vector<Pair>::iterator Vecpa; const int N = , MOD = , M = , NM = ; int Ans;
int n, K;
int fa[N], A[<<], pd[M][M], C[N][];
int dg[NM], dgr[NM], dgs[NM];
int dp[N][M], gp[][<<M]; vector<Pair> E, B[NM];
vector<int> G[N], T[N];
inline void Add(int a, int b) {
G[a].push_back(b);
} inline void Ad(int &a, int b) {
a+=b;
(a>=MOD)? (a-=MOD):();
}
inline int Last_pos(int x, int res=) {
for (x&=(-x); x; x>>=) ++res; return res;
}
inline int Count(int x, int res=) {
for (; x; x>>=) res+=x&; return res;
}
#define Sqr(x) ((LL)(x)*(x))
#define _c2(x) ((LL)(x)*((x)-1)/2) inline int Calc(int n, int m, int K, int res=) {
if (K==) return m;
memset(dg, , sizeof(int)*(n+));
memset(dgr, , sizeof(int)*(n+));
memset(dgs, , sizeof(int)*(n+));
for (Vecpa p=E.begin(); p!=E.end(); ++p) ++dg[(*p).fir], ++dg[(*p).sec];
if (K==) {
for (int *i=dg+; i<=dg+n; ++i) res=(res+_c2(*i))%MOD;
return res;
}
if (K==) {
for (Vecpa p=E.begin(); p!=E.end(); ++p)
res=(res+_c2(dg[(*p).fir]+dg[(*p).sec]-))%MOD;
return res;
}
if (K==) {
for (Vecpa p=E.begin(); p!=E.end(); ++p) {
int u=(*p).fir, v=(*p).sec, X=dg[u]+dg[v]-;
dgr[u]=(dgr[u]+(LL)X*X)%MOD;
dgr[v]=(dgr[v]+(LL)X*X)%MOD;
Ad(dgs[u], X);
Ad(dgs[v], X);
}
for (int i=; i<=n; ++i) {
int sqr=dgr[i], sum=dgs[i], deg=dg[i];
res=(res+(LL)sum*sum-sqr+(LL)sqr*(deg-)-(LL)*(deg-)*sum+(LL)*_c2(deg))%MOD;
}
return (LL)res*(MOD+)/%MOD;
}
int cnt=;
for (int i=; i<=n; ++i) B[i].clear();
for (Vecpa p=E.begin(); p!=E.end(); ++p) {
B[(*p).fir].push_back(Mp((*p).sec, ++cnt));
B[(*p).sec].push_back(Mp((*p).fir, cnt));
}
E.clear();
for (int i=; i<=n; ++i)
for (int j=; j<(int)B[i].size(); ++j)
for (int k=; k<j; ++k)
E.push_back(Mp(B[i][j].sec, B[i][k].sec));
return Calc(m, (int)E.size(), K-);
} inline void Get_dp(int x, int Fa, int K) {
for (Vecit p=G[x].begin(); p!=G[x].end(); ++p) if (*p!=Fa) {
Get_dp(*p, x, K);
}
for (int i=; i<=K; ++i) {
int flg=;
for (int j=; j<i; ++j) if (pd[i][j]) {
dp[x][i]=dp[x][j]; flg=; break;
}
if (flg) continue;
int cnt=;
vector<int> L;
for (Vecit p=T[i].begin(); p!=T[i].end(); ++p) if (*p!=fa[i]) {
if ((int)T[*p].size()==) ++cnt;
else L.push_back(*p);
}
if (cnt+(int)L.size() > (int)G[x].size()-(x!=)) continue;
int ST=<<(int)L.size(), ls=, no=;
memset(gp[], , sizeof(int)*(ST));
memset(gp[], , sizeof(int)*(ST));
gp[no][]=;
for (Vecit v=G[x].begin(); v!=G[x].end(); ++v) if (*v!=Fa) {
int ns=;
for (int j=; j<(int)L.size(); ++j, ns=) if (dp[*v][L[j]]){
for (int k=; k<j; ++k) if (pd[L[j]][L[k]]) ns|=<<k;
int U=(ST-)^ns^(<<j);
for (int sub=U; sub; sub=(sub-)&U) {
Ad(gp[ls][sub|ns|(<<j)], (LL)dp[*v][L[j]]*gp[no][sub|ns]%MOD);
}
Ad(gp[ls][ns|(<<j)], (LL)dp[*v][L[j]]*gp[no][ns]%MOD);
}
for (int st=; st<ST; ++st) {
Ad(gp[ls][st], gp[no][st]), gp[no][st]=;
}
no^=; ls^=;
}
dp[x][i]=(LL)gp[no][ST-]*C[(int)G[x].size()-(int)L.size()-(x!=)][cnt]%MOD;
}
} string Hash_tree(int x, int st, int Fa) {
vector<string> v;
for (Vecit p=T[x].begin(); p!=T[x].end(); ++p) {
if (*p!=Fa && (st>>(*p-))&) v.push_back(Hash_tree(*p, st, x));
}
sort(v.begin(), v.end());
string res="";
for (int i=; i<(int)v.size(); ++i) res+=''+v[i]+'';
return res;
} inline int Hash_to_int(string s) {
int res=, le=s.length();
for (int i=; i<le; ++i) res=(res<<)|(s[i]=='');
return res;
} inline int Build_tree(string tree, int K) {
int x=, cnt=, le=tree.length();
for (int i=; i<le; ++i)
if (tree[i]=='') {
x=fa[x];
if (!x) return -;
} else {
fa[++cnt]=x;
T[x].push_back(cnt);
T[cnt].push_back(x);
E.push_back(Mp(x, cnt));
x=cnt;
if (x>K) return -;
}
if (x!=) {
cerr << tree << endl;
exit();
}
return cnt;
} typedef unsigned long long ULL;
map<ULL, int> Map;
ULL get_hash(int n) {
ULL ret=;
vector<int> v;
for (int i=; i<=n; ++i) {
v.push_back(Hash_to_int(Hash_tree(i, (<<n)-, )));
}
sort(v.begin(),v.end());
for (int i=; i<n; ++i) ret=ret*+v[i];
return ret;
} void DFS(string tree, int K) {
if ((int)tree.length() < *(K-)) {
DFS(tree+'', K);
DFS(tree+'', K);
return;
}
E.clear();
for (int i=; i<=K; ++i) T[i].clear();
if (Build_tree(tree, K) != K) return;
int ss=Hash_to_int(Hash_tree(, (<<K)-, ));
if (~A[ss]) return;
ULL haha=get_hash(K);
A[ss]=(Map.count(haha)? Map[haha] : Map[haha]=Calc(K, K-, ::K)); for (int st=; st<(<<K)-; ++st) {
string gt=Hash_tree(Last_pos(st), st, );
if ((int)gt.length() != *(Count(st)-)) continue;
A[ss]=(A[ss]-A[Hash_to_int(gt)]+MOD)%MOD;
}
memset(pd, , sizeof pd);
for (int i=; i<=K; ++i)
for (int j=i+; j<=K; ++j)
pd[i][j]=pd[j][i]=(Hash_tree(i, (<<K)-, fa[i]) == Hash_tree(j, (<<K)-, fa[j]));
for (int i=; i<=n; ++i)
memset(dp[i], , sizeof(int)*(K+));;
Get_dp(, , K);
int res=;
for (int i=; i<=n; ++i) Ad(res, dp[i][]);
Ad(Ans, (LL)A[ss]*res%MOD);
} int main() {
memset(A, -, sizeof A);
scanf("%d%d", &n, &K);
for (int i=, x, y; i<n; ++i) {
scanf("%d%d", &x, &y); Add(x, y); Add(y, x);
} for (int i=; i<=n; ++i) {
C[i][]=;
for (int j=; j<=i && j<=; ++j) C[i][j]=(C[i-][j]+C[i-][j-])%MOD;
} for (int i=; i<=K+; ++i) DFS("", i);
printf("%d\n", Ans); return ;
}