Network
Time Limit: 2000MS Memory Limit: 65536KTotal Submissions:7879 Accepted: 2253Description
Yixght is a manager of the company called SzqNetwork(SN). Now she's very worried because she has just received a bad news which denotes that DxtNetwork(DN), the SN's business rival, intents to attack the network of SN. More unfortunately, the original network of SN is so weak that we can just treat it as a tree. Formally, there are N nodes in SN's network, N-1 bidirectional channels to connect the nodes, and there always exists a route from any node to another. In order to protect the network from the attack, Yixght builds M new bidirectional channels between some of the nodes.
As the DN's best hacker, you can exactly destory two channels, one in the original network and the other among the M new channels. Now your higher-up wants to know how many ways you can divide the network of SN into at least two parts.
Input
The first line of the input file contains two integers: N (1 ≤ N ≤ 100 000), M (1 ≤ M ≤ 100 000) — the number of the nodes and the number of the new channels.
Following N-1 lines represent the channels in the original network of SN, each pair (a,b) denote that there is a channel between node a and node b.
Following M lines represent the new channels in the network, each pair (a,b) denote that a new channel between node a and node b is added to the network of SN.
Output
Output a single integer — the number of ways to divide the network into at least two parts.
Sample Input
4 1 1 2 2 3 1 4 3 4Sample Output
3Source
POJ Monthly--2007.10.06, Yang Mu
给你一颗无向树，添加附加边，现在让你删一条树边，一条附加边，使不连通，问你有多少种方案，
树上加附加边，形成回路，如果 第一步选树边，第二步必须选附加边
可以求出每条树边被附加边覆盖的次数，如果次数为0，那么选了这条树边后，就已经不连通了，m条附加边中任选，加m即可，如果次数为1，只能有一种对应的方案，如果覆盖次数大于2，那么就不存在方案了，这里采用树上差分方法处理覆盖次数，具体见代码
#include<iostream> #include<cstdio> #include<cstring> #define ll long long #include<algorithm> #define maxn 100005 using namespace std; int n,m; int sta[maxn]; struct edge { int next,v; }edges[maxn*2]; int cnt; int head[maxn]; void init() { memset(head,-1,sizeof(head)); cnt=0; } void addedge(int u,int v) { edges[cnt].next=head[u]; edges[cnt].v=v; head[u]=cnt++; } int dep[maxn]; int f[maxn][25]; void dfs(int u,int fa) { dep[u]=dep[fa]+1; for(int i=0;i<=19;i++) f[u][i+1]=f[f[u][i]][i]; for(int i=head[u];i!=-1;i=edges[i].next) { int v=edges[i].v; if(v==fa) continue; f[v][0]=u; dfs(v,u); } } int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int i=20;i>=0;i--) { if(dep[f[x][i]]>=dep[y]) x=f[x][i]; if(x==y) return x; } for(int i=20;i>=0;i--) { if(f[x][i]!=f[y][i]) { x=f[x][i]; y=f[y][i]; } } return f[x][0]; } int dfs2(int u,int fa) { for(int i=head[u];i!=-1;i=edges[i].next) { int v=edges[i].v; if(v==fa) continue; sta[u]+=dfs2(v,u); } return sta[u]; } int main() { scanf("%d%d",&n,&m); int x,y; init(); memset(sta,0,sizeof(sta)); for(int i=1;i<n;i++) {scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } dfs(1,0); int u,v; for(int i=1;i<=m;i++) {scanf("%d%d",&u,&v); sta[u]++; sta[v]++; sta[lca(u,v)]-=2; } dfs2(1,0); ll ans=0; for(int i=1;i<=n;i++) if(sta[i]==0&&i!=1) ans+=m; else if(sta[i]==1&&i!=1) ans+=1; printf("%lld\n",ans); return 0; }
