POJ 3417 Network
枫林晚
2018-03-23 17:15:50
题目大意：
给定一棵树，有 n-1 条树边，m 条非树边，有两次割边的机会，第一次只能割树边，第二次只能割非树边，问有多少种方案使得两次之后树分为两个部分？
题解：
我们称每条非树边 (x,y) 都把树上 x,y 之间的路径上的每条边“覆盖了一次”。我们只需统计出每条树边被覆盖了次数。若第一步把覆盖 0 次的树边切断，则第二步可以任意切断一条非树边。若第一步把被覆盖 1 次的树边切断，则第二次方法唯一。若第一步把被覆盖 2 次及以上的树边切断，那么第二步无解。
所以我们接下来要解决的问题模型是：给定一张无向图和一颗生成树，求每条“树边”被“非树边”覆盖了多少次。
解决此问题有一个经典做法，我们称之为“树上差分算法”。我们给每个节点一个初始为 0 的权值，然后对每条非树边 (x,y) ,令节点 x 的权值加 1，节点 y 的权值加 1，节点 LCA(x,y) 的权值减 2。最后对这棵生成树进行一次深度优先遍历，求出 F[x] 表示以 x 为根的子树中各节点权值的和。F[x] 就是 x 与它的父节点之间的“树边”被覆盖的次数。时间复杂度 O(N+M)。
--《算法竞赛进阶指南》
注意最后求 ans 时，要从 2 开始，因为 1 的权值一定为 0。
（求树上路径被覆盖次数都可以采用树上差分）
代码：
```cpp
#include<cstdio>
#include<cstring>
#define N 100005
#define int long long
using namespace std;
bool vis[N];
int head[N];
int cf[N],q[N];
int n,m,cnt,ans;
int d[N],f[N][30];
struct Edge{
int to,nxt;
}edge[N<<1];
void add(int x,int y){
edge[++cnt].to=y;
edge[cnt].nxt=head[x];
head[x]=cnt;
}
void dfs(int now){
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(d[to]) continue;
d[to]=d[now]+1;
f[to][0]=now;
for(int k=1;k<=21;k++)
f[to][k]=f[f[to][k-1]][k-1];
dfs(to);
}
}
int lca(int x,int y){
if(d[x]<d[y]) x^=y^=x^=y;
for(int k=21;~k;k--){
if(d[f[x][k]]>=d[y]) x=f[x][k];
}
if(x==y) return y;
for(int k=21;~k;k--){
if(f[x][k]!=f[y][k])
x=f[x][k],y=f[y][k];
}
return f[x][0];
}
void dfs2(int now){
vis[now]=1;
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(!vis[to]){
dfs2(to);
cf[now]+=cf[to];
}
}
}
signed main(){
scanf("%lld%lld",&n,&m);
for(int x,y,i=1;i<n;i++){
scanf("%lld%lld",&x,&y);
add(x,y);add(y,x);
}
d[1]=1;
dfs(1);
for(int x,y,i=1;i<=m;i++){
scanf("%lld%lld",&x,&y);
cf[x]++,cf[y]++;
cf[lca(x,y)]-=2;
}
dfs2(1);
for(int i=2;i<=n;i++){
if(cf[i]==0) ans+=m;
if(cf[i]==1) ans++;
}
printf("%lld",ans);
return 0;
}
```