POJ 3417. Network

发表于 分类于

链接

http://poj.org/problem?id=3417

题意

树形图上另添 $m$ 条附加边，求第一次删去一条主要边，第二次删去一条附加边后树被分割成来两部分的方案数

思路

树上差分 & LCA

每条附加边构成了一个环，使这个环上所有的主要边都被覆盖了一次

若一条主要边被覆盖了 $0$ 次，那随便删掉一条附加边，即满足要求

若一条主要边被覆盖了 $1$ 次，那么删法唯一

若一条主要边被覆盖了 $\ge 2$ 次，无法满足要求

我们给每个点增加一个权值 $d$，在 $x,y$ 间加一条附加边，则让 $d[x]+=1,d[y]+=1，d[lca(x,y)]-=2$

设 $s[x]$ 为点 $x$ 到其父节点的这条边被覆盖的次数：

$s[x]=d[x]+\sum \limits_{y \in son(x)}{s[y]}$

代码

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
63
64
65
66
67
68
69
70
71
72
73
74
#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
using namespace std;
const int N=1e5+5;
int n,m;
int cnt,to[N*2],nxt[N*2],head[N];
int depth[N],f[N][20],d[N],s[N],t,ans;
bool st[N];
void addedge(int u,int v) {
    cnt++;
    to[cnt]=v;
    nxt[cnt]=head[u];
    head[u]=cnt;
}
void bfs() {
    queue<int>q;
    q.push(1);
    depth[1]=1;
    while(q.size()) {
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=nxt[i]) {
            int v=to[i];
            if(depth[v]) continue;
            depth[v]=depth[u]+1;
            f[v][0]=u;
            for(int i=1;i<=t;i++) f[v][i]=f[f[v][i-1]][i-1];
            q.push(v);
        }
    }
}
int lca(int a,int b) {
    if(depth[a]>depth[b]) swap(a,b);
    for(int i=t;i>=0;i--) if(depth[f[b][i]]>=depth[a]) b=f[b][i];
    if(a==b) return a;
    for(int i=t;i>=0;i--) if(f[a][i]!=f[b][i]) a=f[a][i],b=f[b][i];
    return f[a][0];
}
void dfs(int u) {
    st[u]=true;
    for(int i=head[u];i;i=nxt[i]) {
        int v=to[i];
        if(st[v]) continue;
        dfs(v);
        s[u]+=s[v];
    }
    s[u]+=d[u];
}
int main() {
    scanf("%d%d",&n,&m);
    t=(int)log(n)/log(2)+1;
    for(int i=1;i<n;i++) {
        int u,v;
        scanf("%d%d",&u,&v);
        addedge(u,v);
        addedge(v,u);
    }
    bfs();
    for(int i=1;i<=m;i++) {
        int a,b;
        scanf("%d%d",&a,&b);
        d[a]++,d[b]++;
        d[lca(a,b)]-=2;
    }
    dfs(1);
    for(int i=2;i<=n;i++) {
        if(s[i]==0) ans+=m;
        else if(s[i]==1) ans++;
    }
    printf("%d\n",ans);
    return 0;
}