APIO2018 T3，圆方树 的神仙题。
题目链接：Luogu P4630/LibreOJ 2587/APIO2018 T3。
题目
题目描述
比特镇的路网由 \(m\) 条双向道路连接的 \(n\) 个交叉路口组成。
最近，比特镇获得了一场铁人两项锦标赛的主办权。这场比赛共有两段赛程：选手先完成一段长跑赛程，然后骑自行车完成第二段赛程。
比赛的路线要按照如下方法规划：
1、先选择三个两两互不相同的路口 \(s,c,f\)，分别作为比赛的起点、切换点（运动员在长跑到达这个点后，骑自行车前往终点）、终点。
2、选择一条从 \(s\) 出发，经过 \(c\) 最终到达 \(f\) 的路径。考虑到安全因素，选择的路径经过同一个点至多一次。
在规划路径之前，镇长想请你帮忙计算，总共有多少种不同的选取 \(s,c,f\) 的方案，使得在第 \(2\) 步中至少能设计出一条满足要求的路径。
数据范围
| 子任务编号与分数 | 数据范围 | 特殊性质 |
| \(1\)（\(5\) 分） | \(n\leq 10,m\leq 100\) | 无 |
| \(2\)（\(11\) 分） | \(n\leq 50,m\leq 100\) | |
| \(3\)（\(8\) 分） | \(n\leq 10^5\) | 每个交叉路口至多作为两条双向道路的端点。 |
| \(4\)（\(10\) 分） | \(n\leq 1000\) | 在路网中不存在环。 |
| \(5\)（\(13\) 分） | \(n\leq 10^5\) | |
| \(6\)（\(15\) 分） | \(n\leq 1000\) | 对于每个交叉路口，至多被一个环包含。 |
| \(7\)（\(20\) 分） | \(n\leq 10^5\) | |
| \(8\)（\(8\) 分） | \(n\leq 1000,m\leq 2000\) | 无 |
| \(9\)（\(10\) 分） | \(n\leq 10^5,m\leq 2\times 10^5\) |
时空限制
| 题目编号 | 时间限制 | 空间限制 |
| Luogu P4630 | \(1\text{s}\) | \(256\text{MiB}\) |
| LibreOJ 2587 | \(1\text{s}\) | \(1\text{GiB}\) |
| APIO2018 T3 | \(1\text{s}\) | \(1\text{GiB}\) |
题解
思路
首先用广义圆方树把图上问题转化为树上问题。如果你不会圆方树，可以看我的博客「OI」圆方树。
设 \(f _ i\) 表示 \(i\) 的子树内有多少个点对 \((u,v)\) 满足 \((u,i,v)\) 是一条合法路径。
- 若 \(i\) 是圆点，设 \(\text{size} _ i\) 表示 \(i\) 的子树大小（方点不算大小），那么有 \[f _ i=\sum _ {j\in\text{son} _ i}(\text{size} _ i-\text{size} _ j -1)\text{size} _ j\]
- 若 \(i\) 是方点，设 \(\text{deg} _ i\) 表示 \(i\) 代表的点双联通分量的大小（即该方点度数），由于一个任意一个点双联通分量内的点都可以作为中转点（点双联通分量的性质）。所以有 \[f _ i=(\text{deg} _ i-2)\sum _ {j\in\text{son} _ i}(\text{size} _ i-\text{size} _ j)\]
选每一个点直接 \(\texttt{dp}\) 的时间复杂度为 \(\Theta(n^2)\)。
下面考虑 \(\Theta(n)\) 的做法。
不难写出答案的表达式
\[\texttt{ans}=\sum^n _ {i=1}f _ {i}\]
其中 \(f _ i\) 表示以 \(i\) 为根时求得的答案。
我们换种统计方法，假设对于树上的任意一条路径，都是一条合法路径，且此时的方案数为该点两边点数的积再乘上这个点代表的点双联通分量的大小。
当然这样割点被我们重复统计了，在最后算答案的时候我们要将经过割点的答案扣掉，这种做法的时间复杂度为 \(\Theta(n)\)。
代码
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
reg char ch=getchar();
reg int res=0;
while(ch<'0'||'9'<ch)ch=getchar();
while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
return res;
}
const int MAXN=100000+5,MAXM=200000+5;
int n,m,tot;
int deg[MAXN<<1];
ll ans;
namespace Tree{
int cnt,head[MAXN<<1],to[MAXN<<2],Next[MAXN<<2];
inline void Add_Edge(reg int u,reg int v){
Next[++cnt]=head[u];
to[cnt]=v;
head[u]=cnt;
return;
}
inline void Add_Tube(reg int u,reg int v){
Add_Edge(u,v);
Add_Edge(v,u);
return;
}
int fa[MAXN<<1];
int size1[MAXN<<1],size2[MAXN<<1];
inline void DFS1(reg int u){
size1[u]=(u<=n);
for(reg int i=head[u];i;i=Next[i]){
reg int v=to[i];
if(v!=fa[u]){
fa[v]=u;
DFS1(v);
size1[u]+=size1[v];
}
}
return;
}
inline void DFS2(reg int u){
if(fa[u])
size2[u]=size2[fa[u]]+size1[fa[u]]-size1[u];
for(reg int i=head[u];i;i=Next[i]){
reg int v=to[i];
if(v!=fa[u])
DFS2(v);
}
reg int sum=size2[u]+size1[u];
if(u<=n){
for(reg int i=head[u];i;i=Next[i]){
reg int v=to[i];
if(v!=fa[u])
ans+=1ll*(sum-size1[v]-1)*size1[v];
}
ans+=1ll*(sum-size2[u]-1)*size2[u];
}
else{
for(reg int i=head[u];i;i=Next[i]){
reg int v=to[i];
if(v!=fa[u])
ans+=1ll*(sum-size1[v])*size1[v]*(deg[u]-2);
}
ans+=1ll*(sum-size2[u])*size2[u]*(deg[u]-2);
}
return;
}
}
namespace Graph{
int cnt,head[MAXN],to[MAXM<<1],Next[MAXM<<1];
inline void Add_Edge(reg int u,reg int v){
Next[++cnt]=head[u];
to[cnt]=v;
head[u]=cnt;
return;
}
inline void Add_Tube(reg int u,reg int v){
Add_Edge(u,v);
Add_Edge(v,u);
return;
}
int tim,dfn[MAXN],low[MAXN];
int top,S[MAXN];
inline void Tarjan(reg int u){
dfn[u]=low[u]=++tim;
S[++top]=u;
for(reg int i=head[u];i;i=Next[i]){
reg int v=to[i];
if(!dfn[v]){
Tarjan(v);
low[u]=min(low[u],low[v]);
if(low[v]>=dfn[u]){
++tot;
Tree::Add_Tube(tot,u);
Tree::Add_Tube(tot,v);
++deg[u],++deg[v],deg[tot]+=2;
while(S[top]!=v){
Tree::Add_Tube(S[top],tot);
++deg[tot],++deg[S[top]];
--top;
}
--top;
}
}
else
low[u]=min(low[u],dfn[v]);
}
return;
}
}
int main(void){
n=read(),m=read();
tot=n;
for(reg int i=1;i<=m;++i){
static int u,v;
u=read(),v=read();
Graph::Add_Tube(u,v);
}
for(reg int i=1;i<=n;++i)
if(!Graph::dfn[i])
Graph::Tarjan(i);
for(reg int i=1;i<=tot;++i)
if(!Tree::size1[i])
Tree::DFS1(i);
for(reg int i=1;i<=tot;++i)
if(!Tree::size2[i])
Tree::DFS2(i);
printf("%lld\n",ans);
return 0;
}
近期评论