树上贪心。

先预处理出距离。我就用dijkstra皮一下QAQ

显然每个距离大于2的点都需要考虑。

我们贪心处理，优先处理距离最大的。

每次连接距离最大的点的父节点和一号节点。

然后打标记就行了。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6  7 int n,ans; 8 int hd[200005],to[400005],nx[400005],ec; 9 int dis[200005],f[200005];10 bool v[200005];11 12 void edge(int af,int at)13 {14     to[++ec]=at;15     nx[ec]=hd[af];16     hd[af]=ec;17 }18 19 struct data20 {21     int p,d;22     friend bool operator < (data q,data w)23     {24         return q.d>w.d;25     }26 };27 28 priority_queue
         qq;29 30 void dijkstra()31 {32     memset(dis,0x3f,sizeof(dis));33     dis[1]=0;34     qq.push((data){
   1,0});35     while(!qq.empty())36     {37         data nw=qq.top();38         qq.pop();39         if(v[nw.p])continue;40         v[nw.p]=1;41         for(int i=hd[nw.p];i;i=nx[i])42         {43             if((!v[to[i]])&&dis[to[i]]>nw.d+1)44             {45                 dis[to[i]]=nw.d+1;46                 f[to[i]]=nw.p;47                 qq.push((data){to[i],dis[to[i]]});48             }49         }50     }51 }52 53 int main()54 {55     scanf("%d",&n);56     for(int i=1;i
          
           2)qq.push((data){i,-dis[i]});68 else v[i]=1;69 }70 while(!qq.empty())71 {72 data nw=qq.top();73 qq.pop();74 if(v[nw.p])continue;75 int fa=f[nw.p];76 v[fa]=1;77 ans++;78 for(int i=hd[fa];i;i=nx[i])79 {80 v[to[i]]=1;81 }82 }83 printf("%d",ans);84 return 0;85 }