本文转载：http://www.cnblogs.com/YoungNeal/p/8530398.html

题目大意：

给定一棵树，有 n-1 条树边，m 条非树边，有两次割边的机会，第一次只能割树边，第二次只能割非树边，问有多少种方案使得两次之后树分为两个部分？

题解： 我们称每条非树边 (x,y) 都把树上 x,y 之间的路径上的每条边“覆盖了一次”。我们只需统计出每条树边被覆盖了次数。若第一步把覆盖 0 次的树边切断，则第二步可以任意切断一条非树边。若第一步把被覆盖 1 次的树边切断，则第二次方法唯一。若第一步把被覆盖 2 次及以上的树边切断，那么第二步无解。

所以我们接下来要解决的问题模型是：给定一张无向图和一颗生成树，求每条“树边”被“非树边”覆盖了多少次。

解决此问题有一个经典做法，我们称之为“树上差分算法”。我们给每个节点一个初始为 0 的权值，然后对每条非树边 (x,y) ,令节点 x 的权值加 1，节点 y 的权值加 1，节点 LCA(x,y) 的权值减 2。最后对这棵生成树进行一次深度优先遍历，求出 F[x] 表示以 x 为根的子树中各节点权值的和。F[x] 就是 x 与它的父节点之间的“树边”被覆盖的次数。时间复杂度 O(N+M)。

　　　　　　　　　　　　　　　　　　　　　--《算法竞赛进阶指南》 注意最后求 ans 时，要从 2 开始，因为 1 的权值一定为 0。

（求树上路径被覆盖次数都可以采用树上差分）

代码：

#include
     
      #include
      
       #define N 100005#define int long longusing namespace std;bool vis[N];int head[N];int cf[N],q[N];int n,m,cnt,ans;int d[N],f[N][30];struct Edge{    int to,nxt;}edge[N<<1];void add(int x,int y){    edge[++cnt].to=y;    edge[cnt].nxt=head[x];    head[x]=cnt;}void dfs(int now){    for(int i=head[now];i;i=edge[i].nxt){        int to=edge[i].to;        if(d[to]) continue;        d[to]=d[now]+1;        f[to][0]=now;        for(int k=1;k<=21;k++)            f[to][k]=f[f[to][k-1]][k-1];        dfs(to);    }}int lca(int x,int y){    if(d[x]
       
        =d[y]) x=f[x][k];    }    if(x==y) return y;    for(int k=21;~k;k--){        if(f[x][k]!=f[y][k])            x=f[x][k],y=f[y][k];    }    return f[x][0];}void dfs2(int now){    vis[now]=1;    for(int i=head[now];i;i=edge[i].nxt){        int to=edge[i].to;        if(!vis[to]){            dfs2(to);            cf[now]+=cf[to];        }    }}signed main(){    scanf("%lld%lld",&n,&m);    for(int x,y,i=1;i