[CF1029E] Tree with Small Distances

题目传送门

洛谷题面翻译

树上贪心。

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

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

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

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

然后打标记就行了。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<queue>
 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 data
20 {
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<data>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<n;i++)
57     {
58         int ff,tt;
59         scanf("%d%d",&ff,&tt);
60         edge(ff,tt);
61         edge(tt,ff);
62     }
63     dijkstra();
64     memset(v,0,sizeof(v));
65     for(int i=1;i<=n;i++)
66     {
67         if(dis[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 }