题意:给你一颗N个节点树,再给你M条新边(保证不与树边重复)。现在求剪短一条树边和任意M边中的一条边,能将树分成两个联通块的方案
> N (1 ≤ N ≤ 100 000), M (1 ≤ M ≤ 100 000)
一开始想的:暴力,N*M然后检验。。
然后想到树形DP,能不能按照每个节点剪掉它与它父亲节点的树边思考
剪掉这条树边,树边部分肯定不与大树相连接
分类讨论一下新边:
1.如果该子树内任意节点不与大树有新边,那么剪掉任意一条新边都可以产生两个联通块,方案数+M
2.如果该子树内有且仅有1个节点与大树有新边,那么剪掉该边即可产生两个联通块,方案数+1
3.如果该子树内有2个或以上节点与大树有新边,不可能的
问题就是怎么算每一个子树内与树外连接的新边数量
我们发现,两个节点在同子树内,且子树根结点离根节点最远时(最小子树),那么该节点必是两个节点的lca。
设a[i]为以i为根结点连接子树外的新边数量
所以每次连新边的时候,a[x]++,a[y]++,a[lca(x,y)]-=2
然后dfs把每个子树累加
CODE:
#include<iostream>
#include<cstdio>
typedef long long ll;
const int N = 100100;
struct edge{
int next,to;
}e[N<<1];
int last[N],top[N],m,size[N],wson[N],D[N],fa[N];
int cnt;ll dp[N];ll ans=0;
inline void add(int a,int b){
cnt++;
e[cnt].to=b;e[cnt].next=last[a],last[a]=cnt;
}
inline int read(){
int x=0,flag=1;char c=getchar();
while(!isdigit(c)){if(c=='-')flag*=-1;c=getchar();}
while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
return x*flag;
}
inline int dfs1(int x,int f){
size[x]=1;
D[x]=D[f]+1;
fa[x]=f;
for(int i=last[x];i;i=e[i].next){
if(e[i].to==f) continue;
dfs1(e[i].to,x);
size[x]+=size[e[i].to];
if(size[e[i].to]>size[wson[x]]) wson[x]=e[i].to;
}
return 0;
}
inline int dfs2(int x,int topf){
top[x]=topf;
if(!wson[x]) return 0;
dfs2(wson[x],topf);
for(int i=last[x];i;i=e[i].next){
if(e[i].to==fa[x]) continue;
if(e[i].to==wson[x]) continue;
dfs2(e[i].to,e[i].to);
}
return 0;
}
inline int lca(int x,int y){
while(top[x]!=top[y]){
if(D[top[x]]<D[top[y]]) std::swap(x,y);
x=fa[top[x]];
}
return D[x]>D[y]?y:x;
}
inline int dfs(int x){
for(int i=last[x];i;i=e[i].next){
if(e[i].to==fa[x]) continue;
dfs(e[i].to);
dp[x]+=dp[e[i].to];
}
if(!dp[x]&&fa[x]) ans+=m;
if(dp[x]==1) ans++;
return 0;
}
int main(){
int n=read();m=read();
for(int i=1;i<=n-1;++i){
int x=read(),y=read();
add(x,y),add(y,x);
}
dfs1(1,0);
dfs2(1,1);
for(int i=1;i<=m;++i){
int a=read(),b=read();
int LCA=lca(a,b);
dp[a]++,dp[b]++,dp[LCA]-=2;
}
dfs(1);
printf("%lld",ans);
return 0;
}
0 条评论