【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;
}