【LCA+树上差分】Network

传送机:POJ3417

题意:给定一棵树,以及一些新边,每次可以删去1条树边和1条新边,求有多少种方案可以使图不连通。


思路:对于每1条树边,如果这条树边未被覆盖,那么它对答案的贡献为新边的条数 若它仅被覆盖1次,那它对答案的贡献是1(只能删去它所对应的新边) 若它被覆盖2次及以上,那它对答案不做贡献 对于1条新边(u,v),它能覆盖的路径为u->lca(u,v)->v 所以用树上差分统计每条边被覆盖的次数

注意:树剖lca时若重儿子为t,top[t]=top[u](不是top[t]=u) 我已经菜到树剖都不会啦


代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 400000
int n,m,x,y,ans,tot;
int fa[N],deep[N],size[N],head[N],top[N],cnt[N];
struct edge{int v,nxt;}e[N];
void add(int x,int y){e[++tot].v=y; e[tot].nxt=head[x]; head[x]=tot;}
void dfs1(int u){
if (!fa[u]) fa[u]=u;
deep[u]=deep[fa[u]]+1; size[u]=1;
for (int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if (fa[u]!=v){fa[v]=u; dfs1(v); size[u]+=size[v];}
}
}
void dfs2(int u){
if (!top[u]) top[u]=u;
int t=0,v;
for (int i=head[u];i;i=e[i].nxt){v=e[i].v; t=(v!=fa[u] && size[v]>size[t])?v:t;}
if (t==0) return; top[t]=top[u]; dfs2(t);//------我GG的地方
for (int i=head[u];i;i=e[i].nxt){v=e[i].v; if (v!=fa[u] && v!=t) dfs2(v);}
}
int lca(int u,int v){
for (;top[u]!=top[v];u=fa[top[u]]) if (deep[top[u]]<deep[top[v]]) swap(u,v);
return deep[u]<deep[v]?u:v;
}
void count(int u){
for (int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
if (v!=fa[u]){count(v); cnt[u]+=cnt[v];}
}
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<n;i++){scanf("%d%d",&x,&y); add(x,y); add(y,x);}
dfs1(1); dfs2(1);
for (int i=1;i<=m;i++){
scanf("%d%d",&x,&y);
cnt[x]++; cnt[y]++; cnt[lca(x,y)]-=2;
}
count(1);
for (int i=2;i<=n;i++){
if (cnt[i]==0) ans+=m;
if (cnt[i]==1) ans++;
}
printf("%d\n",ans);
return 0;
}