【JZOJ 3896】战争游戏
战争游戏
Description
Input
Output
Sample Input
7 9
1 2
1 3
1 4
1 5
1 6
1 7
2 3
4 5
6 7
Sample Output
18
6
6
6
6
6
6
Data Constraint
这题在一定程度上是挺水的,我拿它讲一讲tarjan求割点。
定义
引用百度百科
设G是一个图,v是G的一个顶点,如果G-v的连通分支数大于G的连通分支数,则称v是G的一个割点
简单的说,割点就是那种拿掉了,图就不连通了的点。
Tarjan
tarjan是很多算法的总称,都由tarjan发明,
主要有 求强连通分量,双联通分量的,求Lca的。
也可以求割点
引入概念
Tarjan中有两个很重要的数组——low , dfn
dfn是指递归时,节点的dfs序,而low数组,
则是该节点与其子树的节点通过返祖边可到达的节点的dfn的最小值。
(注:我的程序中,该节点到父亲的边也算作返祖边)
如图,点D与A之间有一条返祖边,所以节点D的low=1.
求割点
首先对于点x,它的所有子树节点,dfn一定比他大
所以,对于出现了
返祖边只能是在son的子树和x中指来指去。
无法到达x以上的点,即x是割点。
至于横叉边,是绝不可能出现的,因为在DFS中,所谓“横叉边”会当成树边走掉。
回到原题
至于原题,
满足的,显然
是以x为根的子树的节点数
这是会有重复的,感性理解一下,不解释了
重复的部分是
所以
(注:我的代码中,dfm就是low)
#include<cstdio>
#include<cstring>
#define max(x,y) (x>y?x:y)
#define min(x,y) (x<y?x:y)
using namespace std;
int to[200010],next[200010],last[50010],con=0;
int dfn[50010],dfm[50010],sn[50010],dfnn=0;
int fa[50010],f[50010];
int stack[50010],top=0;
int ans[50010],n;
void tarjan(int x)
{
dfn[x]=dfm[x]=++dfnn;
stack[++top]=x;
int a2=0,sa=0;
sn[x]=1;int i;
for(i=last[x];i>0;i=next[i])
{
if(dfn[to[i]]==0)
{
tarjan(to[i]);
dfm[x]=min(dfm[x],dfm[to[i]]);
sn[x]+=sn[to[i]];
if(dfn[x]<=dfm[to[i]])
{
ans[x]+=(n-sn[to[i]]-1)*sn[to[i]];
sa+=sn[to[i]]*sn[to[i]];
a2+=sn[to[i]];
if(dfm[stack[top]]==x)
{
do
{
top--;
}while(stack[top]!=x);
}
}
}
else dfm[x]=min(dfm[x],dfn[to[i]]);
}
ans[x]-=(a2*a2-sa)/2;
}
int main()
{
memset(sn,0,sizeof(sn));
memset(last,0,sizeof(last));
memset(dfn,0,sizeof(dfn));
memset(dfm,0,sizeof(dfm));
int m,i,u,v;
scanf("%d%d",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d%d",&u,&v);
con++;to[con]=v;next[con]=last[u];last[u]=con;
con++;to[con]=u;next[con]=last[v];last[v]=con;
}
tarjan(1);
for(i=1;i<=n;i++)
for(i=1;i<=n;i++) printf("%d\n",ans[i]+n-1);
return 0;
}