传送门
题目大意：给定一棵树和若干条边，问删去树上的一条边和给定的边中的一条使得图不联通的方案数。
题解：
首先注意到，把树上的一条边断掉变成的两个联通块，如果这两个联通块之间恰好有1条给定的边那么方案数+1.
如果没有那么再任意删去一条即可，方案数+（给定的边数）
那么一个显然的做法就是枚举n-1条边然后再枚举m条边然后统计。复杂度O(nm*统计答案的复杂度)。
显然这个东西是可以转移的，考虑dp。
假设当前正在考虑的是x和它的父节点fa的连边，x的儿子记作y。
那么考虑，显然y中有一些边可以当作x的答案，有一些不能。
哪一些不能呢？
显然是跨越y1和y2或者从y连向x的。无论哪一种都满足LCA=x。（如果LCA是x的某个孙子节点那么在那个孙子结点就会被去掉）。
所以这个题就做完了。
代码：
//POJ 3417 #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define MAXN 100010 #define MAXM 200010 #define MAXL 20 using namespace std; struct edges{ int to,pre; }e[MAXM];int sz[MAXN],v[MAXN]; int etop,h[MAXN],ans,mcnt; inline int add_edge(int u,int v) { etop++; e[etop].to=v; e[etop].pre=h[u]; h[u]=etop; return 0; } inline int init_edges() { memset(h,0,sizeof(h)); return etop=0; } inline int inn() { char ch;int x; while((ch=getchar())<'0'||ch>'9'); x=ch^'0'; while((ch=getchar())>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^'0'); return x; } int up[MAXN][MAXL],dep[MAXN]; int dfs(int x,int f) { up[x][0]=f;dep[x]=dep[f]+1; for(int i=1;i<MAXL;i++) up[x][i]=up[up[x][i-1]][i-1]; for(int i=h[x];i;i=e[i].pre) if(e[i].to^f) dfs(e[i].to,x); return 0; } int getLCA(int u,int v) { sz[u]++,sz[v]++; if(dep[u]<dep[v]) swap(u,v); for(int i=MAXL-1;i>=0;i--) if(dep[up[u][i]]>=dep[v]) u=up[u][i]; if(u==v) return u; for(int i=MAXL-1;i>=0;i--) if(up[u][i]!=up[v][i]) u=up[u][i],v=up[v][i]; return up[u][0]; } int getans(int x,int fa) { for(int i=h[x];i;i=e[i].pre) if(e[i].to^fa) { getans(e[i].to,x); sz[x]+=sz[e[i].to]; } sz[x]-=(v[x]<<1); if(sz[x]==1) ans++; else if((!sz[x])&&(x^1)) ans+=mcnt; return 0; } int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF&&(n||m)) { init_edges();mcnt=m; for(int i=1;i<n;i++) { int u,v;scanf("%d%d",&u,&v); add_edge(u,v),add_edge(v,u); } int rt=1;dfs(rt,0); memset(v,0,sizeof(v)); while(m--) v[getLCA(inn(),inn())]++; ans=0;getans(rt,0);printf("%d\n",ans); } return 0; }