网站开发好了如何上线,网站建设参考书,大学生做简历的网站,泰安网站建设价格解析
其实想到了断边按连通块容斥的做法。 但不知道为啥觉得没前途弃了… 悲。
考虑容斥#xff0c;设 f[x][i] 表示 x 子树内与 x 所连的联通块有 i 个节点的方案数#xff0c;第三维朴素是记录连通块个数#xff0c;但其实只需要记一个 0/1 表示奇偶性即可。 然后题解奥…解析
其实想到了断边按连通块容斥的做法。 但不知道为啥觉得没前途弃了… 悲。
考虑容斥设 f[x][i] 表示 x 子树内与 x 所连的联通块有 i 个节点的方案数第三维朴素是记录连通块个数但其实只需要记一个 0/1 表示奇偶性即可。 然后题解奥妙重重的把这一步都取了断奇数次贡献负断偶数次贡献正那直接每次断边的时候把 dp 值取反即可。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N5050;
const int mod1e97;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}inline ll ksm(ll x,ll k,int mod){ll res(1);while(k){if(k1) resres*x%mod;xx*x%mod;k1;}return res;
}int n;ll f[N][N],tmp[2][N],top[N];
vectorinte[N];
ll w[N];
void dfs(int x,int fa){for(int to:e[x]){if(tofa) continue;dfs(to,x); }memset(tmp,0,sizeof(tmp));int now1,pre0,mx1;tmp[now][1]1;for(int to:e[x]){if(tofa) continue;swap(now,pre);memset(tmp[now],0,sizeof(tmp[now]));for(int i0;itop[to];i){for(int j1;jmx;j){(tmp[now][ij]f[to][i]*tmp[pre][j])%mod;}}mxtop[to];}top[x]mx;for(int i1;imx;i){f[x][i]tmp[now][i];(f[x][0]mod-tmp[now][i]*w[i]%mod)%mod;}return;
}signed main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifnread();w[0]1;for(int i1;in;i) w[i](i1)?0:w[i-2]*(i-1)%mod;for(int i1;in;i){int xread(),yread();e[x].push_back(y);e[y].push_back(x);}dfs(1,0);printf(%lld\n,mod-f[1][0]);return 0;
}
