题目链接: C

题目大意: 给出N(N<=10^5)个结点的树，树上某些路是需要维修的

选择某个结点，从这个结点出发到达1结点的路都会被修复

求这些结点的集合，使得这个集合最小并输出集合的结点(SPJ)

解题思路: 建立无向边，从1结点出发开始DFS，没遍历的点就遍历

回溯的时候记录这段路的第一条需要修复的边顶点加入集合

若该结点的孩子结点已经被加入集合，则不需要再加入集合

代码:

#include 
  
   
#include 
   
     #include 
    
      #define MAX 101000 struct snode{ int to,w,next; }Tree[MAX<<2]; int visit[MAX],pre[MAX],sum[MAX],Index,Answer[MAX],Ansn; void Add_edge(int a,int b,int c) { Tree[Index].w=c;Tree[Index].to=b; Tree[Index].next=pre[a]; pre[a]=Index++; } int DFS(int Star,int w) { visit[Star]=1; //记录结点被访问过 int i,v,pd=0,kk=0; for(i=pre[Star];i!=-1;i=Tree[i].next) { if(visit[Tree[i].to]) continue; sum[Star]+=DFS(Tree[i].to,Tree[i].w); } if(w==2||sum[Star]>=1) //若该条路需要被修复||子节点已经被修复 { if(sum[Star]==0) //未被记录则加入集合 { Answer[Ansn++]=Star; } return 1; } else //不需要修复 return 0; } int main() { int n,i,j,a,b,c,ans; while(scanf("%d",&n)!=EOF) { Index=ans=Ansn=0; memset(pre,-1,sizeof(pre)); memset(sum,0,sizeof(sum)); memset(visit,0,sizeof(visit)); for(i=1;i