【题目描述】
传说中的“闇の連鎖”被人们称为 $Dark$。$Dark$ 是人类内心的黑暗的产物,古今中外的勇者们都试图打倒它。经过研究,你发现 $Dark$ 呈现无向图的结构,图中有 $N (N <= 10^5)$ 个节点和两类边,一类边被称为主要边,而另一类被称为附加边。$Dark$ 有 $N – 1$ 条主要边,并且 $Dark$ 的任意两个节点之间都存在一条只由主要边构成的路径。另外,$Dark$ 还有 $M(M<=2\times 10^5)$ 条附加边。你的任务是把 $Dark$ 斩为不连通的两部分。一开始 $Dark$ 的附加边都处于无敌状态,你只能选择一条主要边切断。一旦你切断了一条主要边,$Dark$ 就会进入防御模式,主要边会变为无敌的而附加边可以被切断。但是你的能力只能再切断 $Dark$ 的一条附加边。现在你想要知道,一共有多少种方案可以击败 $Dark$ 。注意,就算你第一步切断主要边之后就已经把 $Dark$ 斩为两截,你也需要切断一条附加边才算击败了 $Dark$ 。
【输入格式】
第一行包含两个整数 $N$ 和 $M$。
之后 $N – 1$ 行,每行包括两个整数 $A$ 和 $B$,表示 $A$ 和 $B$ 之间有一条主要边。
之后 $M$ 行以同样的格式给出附加边。
【输出格式】
输出一个整数表示答案。
数据保证答案不超过 $2^{31}-1$ 。
【输入输出样例】
样例输入:(yam.in)
4 1
1 2
2 3
1 4
3 4
样例输出:(yam.out)
3
【解析】
显然, “主要边” 构成一棵树,而一条 “附加边” 必然会和其两端的 $LCA$ 形成环,如图所示:
那么,每一条主要边存在三种情况:
1、没有被任何环覆盖
2、只被一个环给覆盖
3、被2个及以上的环覆盖
我们来分别看一下:
对于第一种情况,我们切掉一条“主要边”后其实已经将整张图切成了两部分,但根据题意,还要再切掉一条“附加边”,很显然,随便切哪条都可以,因此此时的方案数即为“附加边”的个数 $M$ 。
对于第二种情况,我们切掉一条“主要边”后,由于它是在一个环中,所以只能切掉它所在环中的唯一一条“附加边”,因此此时的方案数为 $1$ 。
对于第三种情况,由于“主要边”存在于2个及以上的环中,因此切掉它之后会使覆盖它的其中两个环合并成一个新环,而我们知道要将一个环切开(此时只有把环切断才能将整张图切开)必须要切两刀,但我们只能再切一刀,所以我们无论如何都不能切开整张图了,因此此时的方案数为 $0$ 。
OK,分类讨论完了,我们该怎么去统计每条边被环覆盖的次数呢?
我们就可以用树上差分来做,用 $cnt[x]$ 表示节点 $x$ 到根节点的距离,则每次读进一条“附加边”时,其两端的 $cnt$ 加一(即该点到根节点的路径上所有边的边权都加一,也就是覆盖次数加一),它们的最近公共祖先(LCA)的 $cnt$ 减二(同理),然后我们就可以像线性的差分求前缀和一样,用dfs求出每个节点的子树的 $cnt[x]$ 的累加和,它就表示节点 $x$ 与它父亲节点之间的边被环覆盖的次数。
最后,根据加法原理,我们只要依次统计每条主要边能产生的方案贡献,累加起来即可。
好了,问题完美解决了!(o゜▽゜)o☆[BINGO!]
【代码展示】
#include<bits/stdc++.h>
#define ud using namespace std
#define itn int
#define ll long long
ud;
const int maxn=200000+10000;
int n,m,t,ans=0;
int top=0,first[maxn];
int cnt[maxn]={};
int d[maxn]={},f[maxn][110]={};
queue<int> q;
struct tree
{
int y;
int next;
}e[maxn<<1];
void add(int x,int y)
{
e[++top].y=y;
e[top].next=first[x];
first[x]=top;
}
inline long long read()
{
long long sum=0,flag=1;
char c;
for(;c<'0'||c>'9';c=getchar())if(c=='-') flag=-1;
for(;c>='0'&&c<='9';c=getchar())sum=(sum<<1)+(sum<<3)+c-'0';
return sum*flag;
}
void bfs()
{
q.push(1);
d[1]=1;
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=first[x];i;i=e[i].next)
{
int y=e[i].y;
if(d[y])
continue;
d[y]=d[x]+1;
f[y][0]=x;
for(int j=1;j<=t;++j)
f[y][j]=f[f[y][j-1]][j-1];
q.push(y);
}
}
}
int lca(int x,int y)
{
if(d[x]>d[y])
swap(x,y);
for(int i=t;i>=0;--i)
{
if(d[f[y][i]]>=d[x])
y=f[y][i];
}
if(x==y)
return x;
for(int i=t;i>=0;--i)
{
if(f[x][i]!=f[y][i])
{
x=f[x][i];
y=f[y][i];
}
}
return f[x][0];
}
void dfs(int x,int fa)
{
for(int i=first[x];i;i=e[i].next)
{
int y=e[i].y;
if(y==fa)
continue;
dfs(y,x);
cnt[x]+=cnt[y];
}
}
int main()
{
n=read();
m=read();
t=(int)(log(n)/log(2))+1;
int xx,yy;
for(int i=1;i<n;++i)
{
xx=read();
yy=read();
add(xx,yy);
add(yy,xx);
}
bfs();
for(int i=1;i<=m;++i)
{
xx=read();
yy=read();
++cnt[xx];
++cnt[yy];
cnt[lca(xx,yy)]-=2;
}
dfs(1,0);
for(int i=2;i<=n;++i)
{
if(!cnt[i])
ans+=m;
if(cnt[i]==1)
++ans;
}
printf("%d\n",ans);
return 0;
}
图炸啦~
t=(int)(log(n)/log(2))+1;
其实cmath自带log2()的
膜拜
大佬 for(int i=2;i<=n;i)
{
if(!cnt[i])
ans+=m;
if(cnt[i]==1)
ans;
}
这个有点不理解,方便解答一下吗
好的。
dfs遍历完后,cnt数组就表示x到它父亲节点这条边被多少个环覆盖,因此从节点2开始统计(1为根节点)。
这里的统计其实是加法原理,简单来说,它可以从任意一条主要边开始斩,而每一条主要边都对应着一个答案,根据加法原理,累加起来就好。
至于答案怎么算,在上面的题解中有分类讨论。
题解我已更新,感谢你的提问。
很详细,赞一个
谢谢!