【NOI P模拟赛】仙人掌（圆方树，树形DP）
2024-09-08 01:36:35
题面
n
n
n 个点，
m
m
m 条边。
1
≤
n
≤
1
0
5
,
n
−
1
≤
m
≤
2
×
1
0
5
1\leq n\leq 10^5,n-1\leq m\leq 2\times10^5
1≤n≤105,n−1≤m≤2×105 。
题解
直接求行列式是不现实的，我们可以通过行列式的定义式来思考解法。
一个会产生贡献的排列，相当于要每个点选一个邻接点当爹，每个点的爹必须不一样。
如果这个点度为 1，那么它和它的邻接点必须配对，然后相当于删掉了。同时这两个点使得该排列的贡献乘上 -1 。类推下去，很容易就能解决一棵树的情况，或者剪掉该图所有枝杈。
然后对于一个干干净净的环，则只有两个大方向：要么相邻的两两配对，要么朝向同一个方向认爹。相邻的配对，总点数只能是偶数，总共两种方案，每个方案的每一对都要使排列贡献乘上 -1，所以总共会使排列的贡献乘上
2
×
(
−
1
)
总
点
数
/
2
2\times(-1)^{总点数/2}
2×(−1)总点数/2 。朝同一个方向认爹，也有两种方案，顺时针和逆时针，每种方案的贡献都是
(
−
1
)
总
点
数
−
1
(-1)^{总点数-1}
(−1)总点数−1 （你想想就知道了），两种方案总共会使排列的贡献乘上
2
×
(
−
1
)
总
点
数
−
1
2\times(-1)^{总点数-1}
2×(−1)总点数−1 。
把这两种模式合并起来怎么办呢？
你可以暴力拓扑删点拆环统计贡献……
也可以用比较清晰的DP做法，在仙人掌上 DP ，建一个圆方树做树形DP。
不过具体的 DP 流程还是根暴力删点拆环差不多
时间复杂度
O
(
n
)
O(n)
O(n) 。
CODE
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<random>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 200005
#define LL long long
#define ULL unsigned long long
#define DB double
#define lowbit(x) (-(x) & (x))
#define ENDL putchar('\n')
#define FI first
#define SE second
LL read() {
LL f=1,x=0;int s = getchar();
while(s < '0' || s > '9') {if(s<0)return -1;if(s=='-')f=-f;s = getchar();}
while(s >= '0' && s <= '9') {x = (x<<3) + (x<<1) + (s^48); s = getchar();}
return f*x;
}
void putpos(LL x) {if(!x)return ;putpos(x/10);putchar('0'+(x%10));}
void putnum(LL x) {
if(!x) {putchar('0');return ;}
if(x<0) {putchar('-');x = -x;}
return putpos(x);
}
void AIput(LL x,int c) {putnum(x);putchar(c);}
const int MOD = 993244853;
int n,m,s,o,k;
int ind[MAXN];
int hd[MAXN],v[MAXN<<1],nx[MAXN<<1],cne;
void ins(int x,int y) {
ind[y] ++;
nx[++ cne] = hd[x]; v[cne] = y; hd[x] = cne;
}
vector<int> g[MAXN];
bool f[MAXN];
int fa[MAXN];
int d[MAXN],id[MAXN];
void dfs0(int x,int ff) {
d[x] = d[fa[x] = ff] + 1;
for(int i = hd[x];i;i = nx[i]) {
int y = v[i];
if(y != ff) {
if(!d[y]) {
dfs0(y,x);
}
else if(d[y] < d[x]) {
int p = x;
f[++ n] = 1;
while(p != y) {
id[p] = n;
p = fa[p];
}
g[n].push_back(y);
g[y].push_back(n);
}
}
}
if(id[x]) {
g[id[x]].push_back(x);
g[x].push_back(id[x]);
}
else {
g[ff].push_back(x);
g[x].push_back(ff);
}
return ;
}
int dp[MAXN][2];
bool df[MAXN];
int tmp[MAXN],tp,tmd[MAXN];
void dfs(int x,int ff) {
if(f[x]) {
int dpp = 1;
for(int i = 0;i < (int)g[x].size();i ++) {
int y = g[x][i];
if(y != ff) {
dfs(y,x);
dpp = dpp *1ll* dp[y][1] % MOD;
}
}
tp = 0;
int ad = 0;
for(int i = 0;i < (int)g[x].size();i ++) {
int y = g[x][i];
tmp[tp ++] = y;
if(y == ff) ad = tp-1;
}
int D[2][2] = {};
D[0][0] = 1;
D[1][1] = 1;
for(int i = (ad+1)%tp;i != ad;i = (i+1)%tp) {
int y = tmp[i];
for(int j = 0;j < 2;j ++) {
int A = (MOD- D[j][1]*1ll*dp[y][1] % MOD + D[j][0]*1ll*dp[y][0] % MOD) % MOD;
int B = D[j][0]*1ll*dp[y][1] % MOD;
D[j][0] = A;
D[j][1] = B;
}
}
int A = 0,B = 0;
(A += D[1][0]) %= MOD;
(B += D[0][0]) %= MOD;
(A += MOD-D[0][1]) %= MOD;
dp[x][0] = A;
dp[x][1] = B;
if(tp & 1) (dp[x][0] += dpp*2ll % MOD) %= MOD;
else (dp[x][0] += MOD-dpp*2ll%MOD) %= MOD;
}
else {
dp[x][1] = 1;
for(int i = 0;i < (int)g[x].size();i ++) {
int y = g[x][i];
if(y != ff) {
dfs(y,x);
if(!f[y]) {
int A = (MOD-dp[x][1] *1ll* dp[y][1] % MOD + dp[x][0]*1ll*dp[y][0]%MOD)%MOD;
int B = dp[x][1] *1ll* dp[y][0] % MOD;
dp[x][0] = A; dp[x][1] = B;
}
else {
int A = (dp[x][1] *1ll* dp[y][0] % MOD + dp[x][0] *1ll* dp[y][1]%MOD) % MOD;
int B = dp[x][1] *1ll* dp[y][1] % MOD;
dp[x][0] = A; dp[x][1] = B;
}
}
}
}
return ;
}
int main() {
freopen("cactus.in","r",stdin);
freopen("cactus.out","w",stdout);
n = read();
m = read();
for(int i = 1;i <= m;i ++) {
s = read();o = read();
ins(s,o);ins(o,s);
}
dfs0(1,0);
dfs(1,0);
AIput(dp[1][0],'\n');
return 0;
}
最新文章
- 指针与数组的区别 —— 《C语言深度剖析》读书心得
- scala getter and setter
- Spring MVC4 纯注解配置教程
- Django admin coercing to Unicode: need string or buffer, tuple found
- emlog在nginx中添加rewrite规则
- php中文转换编码函数
- eNSP的使用
- file以及文件大小转化问题
- [转]Entity Framework走马观花之把握全局
- Flex相关案例及资源搜集
- 使用std::function 把类成员函数指针转换为普通函数指针
- poj 2676 Sudoku ( dfs )
- 使用 AppFuse 的七个理由
- Jquery Mobile左右滑动效果
- NET单元测试的艺术
- 【BZOJ1003】物流运输（动态规划，最短路）
- django中的Q查询
- python之模块 os
- adc 测量子系统
- 在vs 调试进程中找不到 w3wp.exe 进程