题意：给定一棵n个节点的树，然后在给定m条边，去掉m条边中的一条和原树中的一条边，使得树至少分为两部分，问有多少种方案。
神题，一点也想不到做法，
首先要分析出加入一条边之后会形成环，形成环的话，如果去掉该边和环上面没有被其他环覆盖的边，那么便分为两部分了。
这样只需要记录每条边被环覆盖了几次即可，
用dp[u]表示u点的父边被覆盖了几次。
每次新加进来一条边(a,b) dp[a] ++ ,dp[b] ++ , dp[lca(a,b)] -= 2;
所有边处理完之后，遍历一边此树，同时转移状态 dp[u] += dp[v];
#define maxn 100005 struct node { int v,next; }; node e[maxn * 3 ]; int cnt ; int head[maxn * 2 ]; int num ; int E[maxn * 2 + 100],L[maxn * 2 + 100],R[maxn * 2 + 100 ]; int f[maxn * 2 + 100 ][21]; int dp[maxn]; void init() { cnt = 0 ; memset(head,-1,sizeof(head)); } void add(int u ,int v) { e[cnt].v = v ; e[cnt].next = head[u]; head[u] = cnt ++ ; e[cnt].v = u; e[cnt].next = head[v] ; head[v] = cnt ++ ; return ; } void dfs(int u ,int fa,int dep) { E[++num] = u , L[num] = dep , R[u] = num; for(int i = head[u] ;i != -1; i = e[i].next) if(e[i].v != fa) { int v = e[i].v; dfs(v, u, dep + 1 ); E[++num] = u , L[num] = dep; } return; } void initRMQ() { for(int i = 1 ; i <= num ;i ++ ) f[i][0] = i; for(int j = 1 ; (1<<j) <= num ; j++ ) for(int i = 1; i + (1<<j) -1 <= num; i ++ ) if(L[f[i][j-1]] < L[f[i+(1<<(j-1))][j-1]]) //ps:注意下标 f[i][j] = f[i][j-1]; else f[i][j] = f[i+(1<<(j-1))][j-1]; } int lca(int a ,int b) { a = R[a] , b = R[b]; if(a>b) swap(a,b); int k = (log(1.0 + b - a )/log(2.0)); if(L[f[a][k]] < L[f[b-(1<<k)+1][k]] ) return E[f[a][k]]; else return E[f[b-(1<<k)+1][k]]; } void dfs(int u,int fa) { for(int i = head[u] ; i != -1 ; i =e[i].next) if(e[i].v != fa) { int v = e[i].v; dfs(v,u); dp[u] += dp[v]; } return ; } int main() { int n,m; int u,v; while(scanf("%d%d",&n,&m)!=EOF) { init(); for(int i = 0 ; i < n - 1; i ++ ) { scanf("%d%d",&u,&v); add(u,v); } num = 0 ; memset(R,0,sizeof(R)); dfs(1,0,0); initRMQ(); memset(dp,0,sizeof(dp)); for(int i = 0; i < m ; i ++ ) { scanf("%d%d",&u,&v); dp[u] ++ ; dp[v] ++ ; dp[lca(u,v)] -= 2; } dfs(1,0); int sum ; sum = 0 ; for(int i = 2 ;i <= n ; i++ ) // ps:1为根不要选。 { if(dp[i] == 1) sum ++; else if(dp[i] == 0 ) sum += m; } printf("%d ",sum); } return 0; } /* 好题： 离线LCA + 树形DP 分析：加进来一条边(a,b)，会形成一条环 a - lca(a,b) - b 如果去掉(a,b)和没有被其他环覆盖的边，那么就能把树分成两部分。 只要记录dp[u]表示u的负边被环覆盖了几次 对于新加进来的一条边(a,b) dp[a] ++ , dp[b] ++ , dp[lca(a,b)] -= 2;/// 这样处理为完所有新加进来的边之后，在dfs一边，跑完状态转移：dp[u] += dp[v]; 这里就可以把每条环上的边都依次加1，并且因为lca(a,b)的父边不再环上，且已经提前减去了2 这样转移正好可以把减掉的2消去。 注意：这里把lca离线处理成rmq，只需要O(n)的遍历和O(nlogn)的预处理即可。 ST表 并且这里以1为根，后面的状态转移也要以1为根，否则lca就白算了。 */