poj3417lca+树上差分

/*
给定n个点的树,在其中加入m条新边(称为非树边)
现在可以割断一条树边,一条非树边,使图分裂成两个联通块,请问有几种切割方式
对树边进行分情况讨论
如果树边不处在环中,则割断这条树边后可以割断任意条非树边
如果树边仅仅被一个环包含,则割断这条树边后只能割断一条非树边,即环中的那条非树边
如果树边被两个及以上环包含,就不可能有合法的切割方式 那么考虑如何计算树边被多少个环包含
显然每次加入一条非树边(x,y),x->lca(x,y)->y->x就会形成一个环
如果第一次割断这个环上的边,那么第二次就必须割断(x,y)
注意这里的环仅仅指的是非树边沿着两段向上覆盖的环
那么每次加入一条非树边(x,y),就找到lca(x,y),x->lca->y路径上的所有边权+1
如何将路径上所有边权+1:使用树上差分即可,仅仅操作lca,x,y三个点的权值即可 最后枚举每一条边,分类考虑边权=0,1,2的三种情况并求和即可
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cmath>
using namespace std;
#define maxn 200005
struct Edge{int to,nxt;}edge[maxn<<];
int head[maxn],tot,n,m,cnt[maxn];
void init(){
memset(head,-,sizeof head);
tot=;
}
void addedge(int u,int v){
edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++;
} int f[maxn][],d[maxn],t;
void bfs(){
queue<int>q;
q.push();d[]=;
while(!q.empty()){
int u=q.front();q.pop();
for(int i=head[u];i!=-;i=edge[i].nxt){
int v=edge[i].to;
if(d[v])continue;
f[v][]=u;
d[v]=d[u]+;
for(int k=;k<=;k++)
f[v][k]=f[f[v][k-]][k-];
q.push(v);
}
}
}
int lca(int x,int y){
if(d[x]<d[y])swap(x,y);
for(int i=;i>=;i--)
if(d[f[x][i]]>=d[y])x=f[x][i];
if(x==y)return y;
for(int i=;i>=;i--)
if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
return f[x][];
} long long ans;
void dfs(int u,int pre){
for(int i=head[u];i!=-;i=edge[i].nxt){
int v=edge[i].to;
if(v==pre)continue;
dfs(v,u);
cnt[u]+=cnt[v];
}
} int main(){
init();
cin>>n>>m; for(int i=;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);addedge(v,u);
}
bfs();
for(int i=;i<=m;i++){
int u,v;
scanf("%d%d",&u,&v);
cnt[lca(u,v)]-=;
cnt[u]++;cnt[v]++;
} dfs(,);
for(int i=;i<=n;i++)
if(cnt[i]==)ans+=m;
else if(cnt[i]==)ans++;
cout<<ans<<endl;
}
上一篇:Python 工匠:编写条件分支代码的技巧


下一篇:k60引脚图