考虑每一条非树边都连接了祖先和儿子，类似于序列上的问题，从底往上算，当发现如果走到某个环的祖先，且这个环中还没有被选到，那么就将最浅的那条边贪心选择即可
具体实现可以使用bitset维护当前子树的询问，如果这条边选了，那么bitset清空，否则和父亲合并
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 2005 4 struct ji{ 5 int nex,to; 6 }edge[N<<1]; 7 bitset<N>bi[N]; 8 vector<int>v[N]; 9 int E,n,m,x,y,ans,s[N],head[N]; 10 void add(int x,int y){ 11 edge[E].nex=head[x]; 12 edge[E].to=y; 13 head[x]=E++; 14 } 15 void dfs(int k,int fa,int sh){ 16 s[k]=sh; 17 for(int i=head[k];i!=-1;i=edge[i].nex) 18 if (edge[i].to!=fa)dfs(edge[i].to,k,sh+1); 19 } 20 void dfs2(int k,int fa){ 21 bi[k].reset(); 22 for(int i=0;i<v[k].size();i++)bi[k].set(v[k][i]); 23 for(int i=head[k];i!=-1;i=edge[i].nex) 24 if (edge[i].to!=fa)dfs2(edge[i].to,k); 25 if (k==1)return; 26 if (bi[k].test(fa))ans++; 27 else bi[fa]|=bi[k]; 28 } 29 int main(){ 30 while (scanf("%d%d",&n,&m)!=EOF){ 31 if ((!n)&&(!m))return 0; 32 E=ans=0; 33 memset(head,-1,sizeof(head)); 34 for(int i=1;i<=n;i++)v[i].clear(); 35 for(int i=1;i<n;i++){ 36 scanf("%d%d",&x,&y); 37 add(x,y); 38 add(y,x); 39 } 40 dfs(1,0,0); 41 for(int i=n;i<=m;i++){ 42 scanf("%d%d",&x,&y); 43 if (s[x]<s[y])swap(x,y); 44 v[x].push_back(y); 45 } 46 dfs2(1,0); 47 printf("%d ",ans); 48 } 49 }