卡板技术支持 东莞网站建设,怎么把网站放到阿里云,网站怎么做一盘优化排名,wordpress漫画站主题Description 定义线图为把无向图的边变成点#xff0c;新图中点与点之间右边当且仅当它们对应的边在原图中有公共点#xff0c;这样得到的图。 定义弦图为不存在一个长度大于3的纯环#xff0c;纯环的定义是在环上任取两个不相邻的点#xff0c;它们之间都没有边#xff0…Description 定义线图为把无向图的边变成点新图中点与点之间右边当且仅当它们对应的边在原图中有公共点这样得到的图。 定义弦图为不存在一个长度大于3的纯环纯环的定义是在环上任取两个不相邻的点它们之间都没有边也就是不存在没有弦的环的无向图。 现在给出一棵n个点的树你可以在上面添加任意多条边不能重边要求得到的图的线图是弦图求加边的方案数。 n200000 Solution 画图可以发现一个无向图的线图是弦图的充要条件就是不存在长度大于3的环不一定是纯环 也就是说我们加边只能加成三角形并且加的边还不能交叉。 转化后的题意等价于将树上的边分成若干个集合每个集合要么是单独一条边要么是两条相邻的边问方案数。 \(O(n^2)\)的暴力呼之欲出我们记\(f[i][0/1]\)表示处理完\(i\)的子树\(i\)向父亲的这条边是否与子树内的边组合了。 转移的时候我们只需要知道所有儿子中有几个0也就是有几条边需要我们来分配。 不妨再DP预处理出一个数组\(g[i][0/1]\)表示一个点下面挂着i条边要分配集合i的父亲边是否参与的方案数。 我们考虑每次新加一条边要么自成集合要么与之前的某一个组合有\(g[i][0]g[i-1]g[i-2][0]*(i-1),g[i][1]g[i-1][0]*i\) 由于只要知道有几个0这显然可以分治NTT优化这样就做完了。 时间复杂度\(O(n\log^2 n)\) Code 以下代码未经测试完全不能保证正确性。 惨遭证伪请勿参考 #include bits/stdc.h
#define fo(i,a,b) for(int ia;ib;i)
#define fod(i,a,b) for(int ia;ib;--i)
#define N 200005
#define M 524288
using namespace std;
const int mo998244353;
typedef long long LL;
int n,m1,fs[N],nt[2*N],dt[2*N];
LL f[N][2],g[N];
LL ksm(LL k,LL n)
{LL s1;for(;n;n1,kk*k%mo) if(n1) ss*k%mo;return s;
}
void link(int x,int y)
{nt[m1]fs[x];dt[fs[x]m1]y;
}
namespace poly
{int len,st[N],le[N],a[M1];int u1[M1],u2[M1],l2[M1],cf[20],wg[M1],wi[M1],ny[M1],bit[M1];void init(){fo(i,0,18) l2[cf[i](1i)]i;fod(i,M-1,2) if(!l2[i]) l2[i]l2[i1];wg[0]1,wg[1]ksm(3,(mo-1)/M);ny[1]1;fo(i,2,M) wg[i](LL)wg[i-1]*wg[1]%mo,ny[i](-(LL)ny[mo%i]*(mo/i)%momo)%mo;}void prp(int num){int pM/num,wcf[l2[num]-1];fo(i,0,num-1) bit[i](bit[i1]1)|((i1)w),wi[i]wg[i*p];}int inc(int x,int y) {xy;return(xmo)?x-mo:x;}int dec(int x,int y) {x-y;return(x0)?xmo:x;}void DFT(int *a,int num){fo(i,0,num-1) if(ibit[i]) swap(a[i],a[bit[i]]);for(int h1,lnum1;hnum;h1,l1){for(int j0;jnum;j(h1)){int *xaj,*yxh,*wwi,v;for(int i0;ih;i,x,y,wl){v(LL)(*x)*(*y)%mo;*ydec(*x,v),*xinc(*x,v);}}}}void IDFT(int *a,int num){DFT(a,num);fo(i,0,num-1) a[i](LL)a[i]*ny[num]%mo;reverse(a1,anum);}void doit(int l,int r){if(lr) return; int mid(lr)1;doit(l,mid),doit(mid1,r);int numcf[l2[le[l]le[mid1]-1]];prp(num);memset(u1,0,4*num),memset(u2,0,4*num);fo(i,0,le[l]-1) u1[i]a[st[l]i];fo(i,0,le[mid1]-1) u2[i]a[st[mid]i];DFT(u1,num),DFT(u2,num);fo(i,0,num-1) u1[i](LL)u1[i]*u2[i]%mo;IDFT(u1,num);le[l]le[mid1]-1;fo(i,0,le[l]-1) a[st[l]i]u1[i];}
}
using namespace poly;void dfs(int k,int fa)
{for(int ifs[k];i;int[i]) {int pdt[i];if(p!fa) dfs(p,k);}len0;int cnt0;for(int ifs[k];i;int[i]){int pdt[i];if(p!fa){cnt;a[st[cnt]len]f[p][1];a[len]f[p][0];le[cnt]2;}}if(!cnt) f[k][0]1;else{doit(1,cnt);f[k][0]f[k][1]0;fo(i,0,le[1]-1){f[k][0](f[k][0](LL)a[i]*g[i])%mo;if(i) f[k][1](f[k][1](LL)a[i]*g[i-1]%mo*(LL)i)%mo;}}
}
int main()
{cinn;fo(i,1,n-1){int x,y;scanf(%d%d,x,y);link(x,y),link(y,x);}g[0]1,g[1]1;fo(i,2,n) g[i](g[i-1]g[i-2]*(i-1))%mo;init();dfs(1,0);printf(%lld\n,f[1][0]);
} 转载于:https://www.cnblogs.com/BAJimH/p/10945891.html
