题目大意：给出一棵N个结点的无根树，现在要在上面加上M条边，问，有多少种破坏方式(破坏一条树边，一条新边)，能使这张新图变成至少两部分

解题思路：首先，假设添加的边为(u,v)，那么u – > lca(u,v) –> v – >u就形成了一个环了，也就是说，每条添加的边都会在树上形成一个环

本来树上的每条边都是一条桥的，由于加了新的边了，形成了连通分量了，使得边的性质发生了些变化

首先，树边在0个连通分量里面的，那表示该树边还是桥，破坏了它，图肯定能分成两个部分，所以破坏方式就有M种了

接着，树边在1个连通分量里面的，破坏了该树边的话，并不能使图变成两个部分，但可以再破坏一下和他相关的新边，新边一被破坏，那么图肯定能分成至少两个部分了，所以破坏方式有1种

最后，树边在2个或者2个连通分量，那破坏那条树边和和他相关的新边，并没什么卵用，这并不会使图分裂(这个你可以画两个矩形，两个矩形共用一条边，你会发现破话公共边后再破坏别的边，并不会使图变成两份）

那怎么知道树边在几个连通分量里面？
这里有一个技巧，我们假设dp[i]为父结点指向i的这条边(树边)被覆盖的次数，被覆盖了几次，就在几个连通分量里面了
假设新边为(u,v)，u和v的LCA为lca，那么就dp[u]++, dp[v]++, dp[lca] -= 2
为什么要这么做了，因为我们后面会从下面往上更新，从叶结点更新到根结点，那样是不是u–>lca–>根的所有的边的覆盖次数都被增加了dp[u]，所有v –>lca–>根的所有边的覆盖次数都被增加了dp[v]，但因为我们给了dp[lca] -= 2,所以lca–>根的更新都被抵消掉了

#include 
   
     #include 
    
      #define N 100010 #define M 200010 struct Edge{ int from, to, next; }E[M]; struct Query{ int from, to, lca, next; }Q[M]; int head[N], head_Query[N], f[N], dp[N], num[N]; int n, m, tot; bool vis[N]; void AddEdge(int u, int v) { E[tot].from = u; E[tot].to = v; E[tot].next = head[u]; head[u] = tot++; u = u ^ v; v = u ^ v; u = u ^ v; E[tot].from = u; E[tot].to = v; E[tot].next = head[u]; head[u] = tot++; } void AddEdge_Query(int u, int v) { Q[tot].from = u; Q[tot].to = v; Q[tot].next = head_Query[u]; head_Query[u] = tot++; u = u ^ v; v = u ^ v; u = u ^ v; Q[tot].from = u; Q[tot].to = v; Q[tot].next = head_Query[u]; head_Query[u] = tot++; } void init() { memset(head, -1, sizeof(head)); tot = 0; int u, v; for (int i = 1; i < n; i++) { scanf(%d%d, &u, &v); AddEdge(u, v); } memset(head_Query, -1, sizeof(head_Query)); memset(dp, 0, sizeof(dp)); tot = 0; for (int i = 0; i < m; i++) { scanf(%d%d, &u, &v); AddEdge_Query(u, v); dp[u]++; dp[v]++; } } int find(int x) { return x == f[x] ? x : f[x] = find(f[x]); } void Tarjan(int u) { vis[u] = true; f[u] = u; for (int i = head[u]; ~i; i = E[i].next) { int v = E[i].to; if (!vis[v]) { Tarjan(v); f[v] = u; } } for (int i = head_Query[u]; ~i; i = Q[i].next) { int v = Q[i].to; if (vis[v]) Q[i].lca = find(v); } } int dfs(int u) { vis[u] = true; for (int i = head[u]; ~i; i = E[i].next) { int v = E[i].to; if (!vis[v]) { int t = dfs(v); num[++tot] = t; dp[u] += t; } } return dp[u]; } void solve() { memset(vis, 0, sizeof(vis)); Tarjan(1); for (int i = 0; i < tot; i += 2) dp[Q[i].lca] -= 2; memset(num, 0, sizeof(num)); memset(vis, 0, sizeof(vis)); tot = 0; dfs(1); int ans = 0; for (int i = 1; i <= tot; i++) if (num[i] == 1) ans++; else if (num[i] == 0) ans += m; printf(%d , ans); } int main() { while (scanf(%d%d, &n, &m) != EOF) { init(); solve(); } return 0; }
    
   

?