题目
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
f
u
2
g
v
f_u times 2times g_v
-
v
v
(
f
u
+
g
u
)
f
v
(f_u+g_u) times f_v
g
u
=
∏
(
2
g
v
)
g_u = prod(2 times g_v)
gu=∏(2gv)。
记
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_u=2^{V_u+E_u}-2^{E_u},g_u=2^{E_u}
fu=2Vu+Eu−2Eu,gu=2Eu。
P4 统计答案
假定只选
i
i
i 子树内的点,此时子树外的边均可选可不选。然而这样在
i
i
i 祖先处统计会重复计算
i
i
i 的贡献,强制不选
i
→
f
a
i
i to fa_i
i→fai 这条边即可,其余子树外的边任意。
P5
#include
#include
#define int long long
using 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 i=head1[u]; i; i=e1[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; i=e2[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 i=1; im; i++) pw[i] = (pw[i-1] 1) % mod;
for(int i=1; im; i++)
{
int u, v;
cin >> u >> v;
add1(u, v); add1(v, u);
}
Tarjan(1, 0);
for(int i=1; in; i++)
{
if(!belong[i]) ++ cnt, dfs0(i);
}
for(int i=2; 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 i=1; icnt; i++) E[i] >>= 1;
dfs(1, 0);
cout ans;
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
在计算机视觉领域,YOLO(You Only Look Once)是一种流行的目标检测算法,它能够快速准确地识别图像中的物体,并输出其边界框和类别信息。YOLOv5是YOLO系列的最新版本,相比之前版本在精度和速度上都有了显著提升。但在运行YOLOv5的tra…