一道好题
N个点N-1条边,众所周知这是一棵树
我们每连接一条附加边,就增加了一个环
如果一条边不在环上,那么我们拆除这条边后拆除任意附加边就可以了
如果一条边在一个环上,那么我们拆除这条边后必须要拆除构成这个环的附加边
如果一条边在多个环上,那么无论如何都不能将这张图从此处断开
综上,我们需要计算每条边上的环的数量
如果我们在结点a和b处添加附加边,哪些边会在环上?
因为边上的权值不好计算,我们可以用点的权值代替这个点到它父结点这条边上的权值
显然遍历这些点会T,我们考虑差分,即
sum[a]++,sum[b]++,sum[f]-=2;
最后dfs一边就好了
void dfs(int x){
v[x]=1;
for(int i:t[x])
if(!v[i]){
dfs(i);
sum[x]+=sum[i];
}
if(x==1) return ;
if(sum[x]==0) ans+=m;
if(sum[x]==1) ans+=1;
}