给你一棵树和m条边，问你在这些边里面最多能够挑出多少条边，使得这些边之间不能相互交叉。
思路：
lca+贪心，首先对于给的每个条边，我们用lca求出他们的公共节点，然后在公共节点的深度排序，排序之后我们先从最深的开始，每次判断当前的这条边的两点是否用过，如果没用过，那么就把以当前两点的公共点为树根的子树全部标记上，然后答案+1，就这样一直遍历到最后就行了，一开始敲了一个，TLE了，各种优化之后还是TLE了，最后没办法了，用了一下自己存的一个LCA的模板，这个比我自己写的LCA快，所以就AC了，思路就是贪心+LCA。
#include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #define MAXN 110000 #define MAXM 210000 using namespace std; //********************************************************* int n; struct EDGE { int v, next, w; }edge[MAXM]; int head[MAXN], e; int index, tmpdfn; int f[2 * MAXN], id[MAXN], vis[MAXN], pos[MAXN], dis[MAXN]; int mi[2 * MAXN][18]; void init() { memset(head, -1, sizeof(head)); e = 0; index = tmpdfn = 0; memset(vis, 0, sizeof(vis)); dis[1] = 0; } void add(int u, int v, int w) { edge[e].v = v; edge[e].w = w; edge[e].next = head[u]; head[u] = e++; } void dfs(int u) { vis[u] = 1; int tmp = ++tmpdfn; f[++index] = tmp; id[tmp] = u; pos[u] = index; for(int i = head[u]; i != -1; i = edge[i].next) { int v = edge[i].v; if(!vis[v]) { dis[v] = dis[u] + edge[i].w; dfs(v); f[++index] = tmp; } } } void rmqinit(int n, int *w) { for(int i = 1; i <= n; i++) mi[i][0] = w[i]; int m = (int)(log(n * 1.0) / log(2.0)); for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++) { mi[j][i] = mi[j][i - 1]; if(j + (1 << (i - 1)) <= n) mi[j][i] = min(mi[j][i], mi[j + (1 << (i - 1))][i - 1]); } } int rmqmin(int l,int r) { int m = (int)(log((r - l + 1) * 1.0) / log(2.0)); return min(mi[l][m] , mi[r - (1 << m) + 1][m]); } int LCA(int l, int r) { if(pos[l] > pos[r]) swap(l, r); int ans = rmqmin(pos[l], pos[r]); return id[ans]; } //********************************************************** typedef struct { int a ,b ,ggdeep ,lca; }EDGEE; EDGEE edgee[110000]; bool camp(EDGEE a ,EDGEE b) { return a.ggdeep > b.ggdeep; } int use[110000]; void mk_dfs(int x) { use[x] = 1; for(int k = head[x] ;k + 1 ;k = edge[k].next) { int to = edge[k].v; if(use[to] || dis[x] + 1 != dis[to]) continue; mk_dfs(to); } } int main() { int u, v, w, l, r ,m; while(~scanf("%d%d", &n, &m)) { init(); for(int i = 1 ;i < n ;i ++) { scanf("%d %d" ,&u ,&v); add(u ,v ,1); add(v ,u ,1); } for(int i = 1 ;i <= m ;i ++) scanf("%d %d" ,&edgee[i].a ,&edgee[i].b); dfs(1); rmqinit(index, f); for(int i = 1 ;i <= m ;i ++) { int lca = LCA(edgee[i].a ,edgee[i].b); edgee[i].ggdeep = dis[lca]; edgee[i].lca = lca; } sort(edgee + 1 ,edgee + m + 1 ,camp); memset(use ,0 ,sizeof(use)); int ans = 0; for(int i = 1 ;i <= m ;i ++) { if(use[edgee[i].a] || use[edgee[i].b]) continue; ans ++; mk_dfs(edgee[i].lca); } printf("%d " ,ans); } return 0; }