| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 3749 | Accepted: 1067 |
Description
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 4
Sample Output
3
一颗n个节点，n-1条边的树，再加m条边，去掉原来的一条边，m条边里的一条边，有多少种方法使得树不连通，
设dp[i]表示i上方的边被几个环覆盖，对于新加的每一条边a,b,dp[a]++,dp[b]++,dp[lca(a,b)]-=2,然后树形dp，
找出每一条边被几个环覆盖，假如没有被环覆盖，答案加m，假如被一个环覆盖，答案加1，其他的无用，然后就可以得到答案。
代码：
/* ***********************************************
Author :rabbit
Created Time :2014/3/29 11:40:24
File Name :E.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
const int maxn=100010;
int head[maxn],tol,fa[maxn][20],dep[maxn],dp[maxn];
struct node{
int next,to;
}edge[5*maxn];
void addedge(int u,int v){
edge[tol].to=v;
edge[tol].next=head[u];
head[u]=tol++;
}
void bfs(int root){
queue<int> q;
fa[root][0]=root;dep[root]=0;
q.push(root);
while(!q.empty()){
int u=q.front();q.pop();
for(int i=1;i<20;i++)fa[u][i]=fa[fa[u][i-1]][i-1];
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;if(v==fa[u][0])continue;
dep[v]=dep[u]+1;fa[v][0]=u;
q.push(v);
}
}
}
int lca(int x,int y){
if(dep[x]<dep[y])swap(x,y);
for(int i=0;i<20;i++)if((dep[x]-dep[y])&(1<<i))x=fa[x][i];
if(x==y)return x;
for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
void dfs(int u,int fa){
for(int i=head[u];i!=-1;i=edge[i].next){
int v=edge[i].to;
if(v==fa)continue;
dfs(v,u);
dp[u]+=dp[v];
}
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int n,m;
while(~scanf("%d%d",&n,&m)){
memset(head,-1,sizeof(head));tol=0;
memset(dp,0,sizeof(dp));
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
bfs(1);
for(int i=1;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
dp[a]++;dp[b]++;
dp[lca(a,b)]-=2;
}
dfs(1,-1);
int ans=0;
for(int i=2;i<=n;i++){
if(dp[i]==0)ans+=m;
if(dp[i]==1)ans++;
}
cout<<ans<<endl;
}
return 0;
}
POJ 3417 lca+树形dp,布布扣,bubuko.com
原文：http://blog.csdn.net/xianxingwuguan1/article/details/22582027