线图

题目描述

九条可怜是一个热爱出题的女孩子。

今天可怜想要出一道和图论相关的题。在一张无向图 $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

output

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 ;

 }

巴特西

【ZJOI 2018】线图（树的枚举，hash，dp）

线图

题目描述

输入输出格式

样例一

限制与约定

最新文章

热门文章