重庆本地网站论坛有哪些,网络推广协议合同范本,网站备案多个域名,最便宜的域名注册商题目
P1 边双缩点
观察样例二#xff0c;可以发现边双内的边可选可不选。由此考虑边双缩点#xff0c;Tarjan 找桥即可#xff0c;缩点后变成一棵树。
P2 设计状态
用最终合法答案形态截这颗树#xff0c;设计 f u f_u fu 表示 u u u 子树内非空#xff0c;且子树…题目
P1 边双缩点
观察样例二可以发现边双内的边可选可不选。由此考虑边双缩点Tarjan 找桥即可缩点后变成一棵树。
P2 设计状态
用最终合法答案形态截这颗树设计 f u f_u fu 表示 u u u 子树内非空且子树内军营到 u u u 的边均被保护的方案数。
P3 转移
为方便转移记 g u g_u gu 表示 u u u 子树空的方案数遍历 u u u 的儿子 v v v v v v 不选则 v v v 之前非空 f u × 2 × g v f_u \times 2\times g_v fu×2×gv。 v v v 选 ( f u g u ) × f v (f_ug_u) \times f_v (fugu)×fv。 g u ∏ ( 2 × g v ) g_u \prod(2 \times g_v) gu∏(2×gv)。
记 u u u 所在边双点数为 V u V_u Vu边数为 E u E_u Eu。初值 f u 2 V u E u − 2 E u , g u 2 E u f_u2^{V_uE_u}-2^{E_u},g_u2^{E_u} fu2VuEu−2Eu,gu2Eu。
P4 统计答案
假定只选 i i i 子树内的点此时子树外的边均可选可不选。然而这样在 i i i 祖先处统计会重复计算 i i i 的贡献强制不选 i → f a i i \to fa_i i→fai 这条边即可其余子树外的边任意。
P5
#include iostream
#include vector
#define int long longusing namespace std;const int N 5e5 5;
const int M 1e6 5;
const int mod 1e9 7;int n, m, pw[N M];struct Edge{int to, nxt;
}e1[M 1], e2[M 1];int tot1 1, head1[N];
void add1(int u, int v)
{e1[tot1] {v, head1[u]}; head1[u] tot1;
}int tot2 1, head2[N];
void add2(int u, int v)
{e2[tot2] {v, head2[u]}; head2[u] tot2;
}int low[N], dfn[N], idx;
bool bridge[M 1];
void Tarjan(int u, int from)
{low[u] dfn[u] idx;for(int ihead1[u]; i; ie1[i].nxt){if((i ^ 1) from) continue;int v e1[i].to;if(!dfn[v]) // tree edge{Tarjan(v, i);low[u] min(low[u], low[v]);if(low[v] dfn[v])bridge[i] bridge[i ^ 1] 1;}else low[u] min(low[u], dfn[v]); // back edge}
}int cnt, belong[N], V[N], E[N];
void dfs0(int u)
{belong[u] cnt, V[cnt] ;for(int i head1[u]; i; i e1[i].nxt){int v e1[i].to;if(belong[v] or bridge[i]) continue;dfs0(v);}
}int ans, siz[N], f[N], g[N];
void dfs(int u, int from)
{f[u] pw[E[u]] * (pw[V[u]] - 1) % mod,g[u] pw[E[u]], siz[u] E[u];for(int i head2[u]; i; ie2[i].nxt){if((i ^ 1) from) continue;int v e2[i].to;dfs(v, i);siz[u] siz[v] 1;f[u] f[u] * 2 * g[v] % mod (f[u] g[u]) * f[v] % mod; f[u] % mod;g[u] * 2 * g[v]; g[u] % mod;}if(u 1) ans f[u], ans % mod;else ans f[u] * pw[m - siz[u] - 1] % mod, ans % mod;
}signed main()
{cin n m;pw[0] 1; for(int i1; im; i) pw[i] (pw[i-1] 1) % mod;for(int i1; im; i){int u, v;cin u v;add1(u, v); add1(v, u);}Tarjan(1, 0);for(int i1; in; i){if(!belong[i]) cnt, dfs0(i);}for(int i2; itot1; i){int u e1[i].to, v e1[i ^ 1].to;if(belong[u] belong[v]) E[belong[u]] ;else add2(belong[u], belong[v]);}for(int i1; icnt; i) E[i] 1;dfs(1, 0);cout ans;
}
