算法思路

可以说是一道LCA + 树上差分的模板题
回想一下思路： 本题是给定一棵树，然后在加入一些非树边，最后问删掉一跳树边和一条非树边使树不连通的方案数。
设想一下，当这棵树只有树边的时候，然后加入任意一条非树边，都可以在树上构成环， 因此我们如果删除环上的任意一条树边，那么只要删除那条非树边才可以满足题意，因此，这道题就可以转化一下，
求出一个数组f[i]代表i与父节点相连的边与每次加入的非树边构成几次环。
如果f[i] = 0 表示如果把i砍掉那么任意砍掉一条非树边就可以满足题意。
如果f[i] = 1 表示该点与父节点所连的边和一条非树边构成了环，因此如果要砍掉这条边同时也必须要砍掉那条非树边才可以满足题意。
如果f[i] = n(n >= 2) 那么砍掉i与父节点所连的边并且最少要砍掉n 条边才可以满足题意，因此不满足只看一条非树边，pass.
终上所述，我们求的答案就是看f[i]的值是多少，再计算即可。
但是因为每次都要把与非树边构成的环的树边加上1,如果暴力的话O(nm)会超时，因此要换一种做法。
因为每次把一段的树上的路径加上1那么刚好可以用差分的思想来做，时间为O(1)，最后算一下总和为O(n + m)时间完全ok，
那么怎么做呢？
我们刚才已经设f[i]数组代表i与父节点所连的边构成几次环。设d[i]为f[i]的差分数组
如果说a, b为一条非树边就把d[a] , d[b] , d[lca(a, b)] -= 2; f[i] 为以i为根节点的所有子节点的值。
那么只需要做一半dfs()遍历即可求出答案。

int res = 0;//最终答案
int dfs(int u, int fa) // 表示以u为根节点的的所有值的和加上u到父节点的值。
{
    int ans = d[u]; // 把u到父节点的值加上
    for(int i = h[u]; ~i; i = ne[i];
    {
        int j = e[i];
        if(j != fa)
        {
            int t = dfs(j, t); 
            if(t == 0)res += m;// 第一种情况
            else if(t == 1)res ++;// 第二种情况
            ans += t;
        }
    return ans; 
    }
}

秦淮安大佬的题解
Hen不错的题解